[Algorithm] LeetCode 5 - Longest Palindromic Substring

시간 복잡도

 \( O(N^2) \)

 

문제 링크

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

---

 

 이번 문제의 유형은 palindrome으로써 문자열 중 가장 긴 palindrome을 찾는 문제입니다. Palindrome이란 거꾸로 뒤집어도 똑같은 문자열을 뜻합니다.

 

 가장 쉬운 방법으로는 모든 문자열에 대하여 palindrome 여부를 검사해 가장 길이가 긴 문자열을 답으로 제출하면 됩니다. 시간을 계산하면, 모든 문자열은 이중 for문을 이용해  \( O(N^2) \)의 시간, 문자열마다 palindrome 여부를 검사하는 \( O(N) \) 시간이 걸리므로 총 \( O(N^3) \)의 시간 복잡도를 가집니다. \( O(N^3) \)의 시간 복잡도는 상당히 비효율적인 시간이므로 다른 방법을 생각해야 합니다.

 

 이 방법의 문제점은 매번 substring의 시작점을 기준으로 무조건 전체 문자열의 끝까지 탐색을 해야한다는 점입니다. 왜냐하면 마지막 index 전까지 palindrome 조건을 만족하지 않다가 마지막 index를 문자열에 포함시키면서 조건을 만족할 수 있기 때문입니다. 그래서 중복된 문자열의 검사가 존재합니다.

 

 하지만 이러한 문제점을 보완한 방법이 있습니다. 시작점을 정해놓고 끝 문자열까지 탐색하는 것이 아니라 문자열의 가운데부터 시작해 양 옆으로 넓혀가며 가장 긴 palindrome을 찾습니다. Palindrome의 특성상 중앙으로부터 대칭이 아니면 조건을 만족하지 않기 때문에 넓혀가는 과정에서 하나라도 문자열이 일치하지 않는다면 이후 과정은 palindrome의 조건을 만족하지 않습니다.

 

 그래서 위의 모든 경우의 수를 탐색하는 과정과 다르게 이 방법의 장점은 중간점을 기준으로 검사하다가 조건을 만족하지 않으면 끊고 기준점을 옮길 수 있다는 점입니다. 그래서 시간 복잡도를 계산하면 기준점을 처음부터 끝까지 옮기는데 \( O(N) \), 각 기준점을 중앙으로 위치해 양 옆으로 넓히는데 \( O(N) \) 입니다. 그래서 최종적으로는 \( O(N^2) \) 입니다.

 

 알고리즘을 구현하는데 있어 주의할 점은 palindrome 문자열의 길이가 홀수일 때와 짝수일 때로 나눠줘야 합니다. 홀수일 때는 기준점 M을 기준으로 양 옆으로 넓히면서 검사하고, 짝수일 때는 기준점 M과 M+1 비교를 시작으로 양 옆으로 넓혀주면 답을 구할 수 있습니다.

 

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        res = ""
        
        if len(s) <= 1 : return s
        
        for i in range(len(s)):
            res1 = self.check_palindromic(s, i, i)
            res2 = self.check_palindromic(s, i, i+1)
            
            if len(res) < len(res1):
                res = res1
            if len(res) < len(res2):
                res = res2
            
        return res
            
            
    def check_palindromic(self, s, l, r):
        idx = -1
        for i in range(len(s)):
            if l-i < 0 or r+i >= len(s): break
            if s[l-i] != s[r+i]: break
                
            idx = i
                    
        return s[l-idx:r+idx+1] if idx != -1 else ""