LeetCode5 - Longest Palindromic Substring

lc5 - longest palindromic substring

Longest Common Substring(최장 공통 부분 문자열) 문제는 여러 개의 입력 문자열이 있을 때 서로 공통된 가장 긴 부분 문자열을 찾는 문제로 Daynamic Programming으로 풀 수 있는 문제다.

그러나 이 문제의 경우 Two Pointer 를 사용하는 게 더 직관적이고 성능이 좋다. 팰린드롬 판별만 하면 된다는 점을 착안하여, 중앙을 중심으로 확장해 나가면서 판별하면 된다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left, right):
            while left >= 0 and right <= len(s) and s[left] == s[right-1]:
                left -= 1
                right += 1
            return s[left + 1 : right - 1]
        
        if len(s) < 2 or s == s[::-1]:
            return s
        
        result = ''
        
        for i in range(len(s) - 1):
            result = max(result,
                         expand(i, i + 1),
                         expand(i, i + 2),
                         key = len)            
        return result
    
a = Solution()
print(a.longestPalindrome('badad'))

2칸, 3칸으로 구성된 투 포인터가 앞으로 전진한다. 만약 팬린드롬이 판별될 경우 그 자리에 멈추고, 포인터가 확장해 나간다.

항상 예외 처리를 고려해야 한다. 이 문제에선 문자열의 길이가 len(1)인 것과 reverse()해도 변화가 없는 경우다.