피드로 돌아가기
Dev.toBackend
원문 읽기
O(N^2) 시간 복잡도와 O(1) 공간 효율을 달성한 Expand Around Center 전략
LeetCode Solution: 5. Longest Palindromic Substring
AI 요약
Context
모든 부분 문자열을 검사하는 Brute-force 방식의 O(N^3) 시간 복잡도 한계 직면. 단순 반복문 기반의 검증 로직으로 인한 불필요한 연산 중복 발생.
Technical Solution
- Palindrome의 대칭성 원리를 활용한 중심점 기준 확장 구조 설계
- 홀수 길이 및 짝수 길이 Palindrome 대응을 위한 두 가지 Center 포인트 정의
expand_around_center헬퍼 함수를 통한 양방향 인덱스 확장 로직 구현- 경계값 체크와 문자 일치 여부 판단을 통한 최적의 확장 범위 도출
- 발견된 최대 길이에 따른 Start 및 End 인덱스의 동적 갱신 체계 구축
- Dynamic Programming 대비 메모리 사용량을 최소화한 포인터 기반 탐색 방식 채택
실천 포인트
- 문자열 대칭성 검사 시 단일 중심점과 이중 중심점 케이스를 모두 고려했는지 확인 - DP 기반 해결책 도입 전 포인터 조작만으로 공간 복잡도를 O(1)로 낮출 수 있는지 검토 - 경계 조건(Out of Bounds) 처리를 통한 런타임 에러 방지 로직 적용