리트코드 - longest-palindromic-substring

https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

팰린드롬은 앞뒤로 읽어도 같은 문자열을 의미한다. 이번 문제는 주어진 문자열 s 중 가장 긴 팰린드롬 부분 문자열을 찾는 것이다.

문자열의 각 위치에서 팰린드롬의 가능성을 탐색하고, 가장 긴 팰린드롬 부분 문자열을 찾는 방법을 찾아야 한다.

중심 확장으로 문제 풀이

1. 중심 확장: 각 문자와 문자 사이를 팰린드롬의 '중심'으로 가정하고, 양쪽으로 확장해 나가며 팰린드롬을 확인한다.
2. 홀수 및 짝수 길이 처리: 팰린드롬은 홀수 길이(aba)와 짝수 길이(abba) 모두 가능하다. 이를 위해 각 문자를 중심으로 하거나, 두 문자 사이를 중심으로 하는 두 가지 경우를 모두 고려해야 한다.
3. 가장 긴 팰린드롬 탐색: 모든 가능한 중심에서 가장 긴 팰린드롬 부분 문자열을 찾는다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check(l, r):
            while(l >= 0 and r < len(s) and s[l] == s[r]):
                l -= 1
                r += 1
            return s[l+1:r]
        
        res = ""
        for i in range(len(s)):
            odd = check(i, i)
            even = check(i, i+1)
            
            if len(odd) > len(res):
                res = odd
            if len(even) > len(res):
                res = even
        return res

• 시간 복잡도: O(n^2)
  • 문자열의 각 위치에서 팰린드롬을 확인하는 데 O(n) 시간이 소요된다. 문자열의 길이를 n이라 할 때, 모든 중심에서 팰린드롬을 확인하므로 총 O(n^2) 시간이 필요하다.
• 공간 복잡도: O(1)
  • 추가적인 공간을 사용하지 않고, 입력 문자열 내에서 직접 팰린드롬을 확인한다. 따라서 공간 복잡도는 O(1).

시간 복잡도를 줄일 수 있는 풀이가 뭐가 있을까..?