LeetCode 5. Longest Palindromic Substring

문제

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

걸린 시간

-

풀이

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = ' ' + s
        n = len(s)
        dp = [[False]*n for _ in range(0, n)]
        for j in range(1, n):
            dp[1][j] = True
        for j in range(2, n):
            if s[j] == s[j-1]:
                dp[2][j] = True 
        for i in range(3, n): # palindrome length
            for j in range(i, n): # palindrome last character
                if dp[i-2][j-1]:
                    start = j-i+1
                    end = j
                    dp[i][j] = True if s[start] == s[end] else False
        ans = ""
        for i in range(1, n):
            for j in range(i, n):
                if dp[i][j]:
                    start = j-i+1
                    end = j
                    ans = s[start:end+1]
        return ans

다른 풀이

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left: int, right: int) -> str:
            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(0, len(s)-1):
            result = max(result
                        ,expand(i, i+1)
                        ,expand(i, i+2)
                        ,key = len)
        return result

크기가 2, 3 인 투 포인터가 문자열의 모든 위치에서 출발한다.

해당 위치의 값이 펠린드롬이면 계속해서 검사 & 확장하고 그렇지 않으면 축소되어 반환된다.

dp 풀이에 비해서 실행속도가 훨씬 빠르다.