LeetCode: 5. Longest Palindromic Substring

 

Dynamic Programming을 이용한 방법:

X + <Palindrome Substring> + X 는 Palindrome Substring이다는 특성을 이용한다.

위를 bottom-up으로 구현하려면, 문자열의 길이가 커지는 순(1, 2, 3, ....) 으로 DP를 연산하면 된다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ret = ""
        
        is_Palindrome = [[False] * len(s) for _ in range(len(s))]
        for i in range(len(s)):
            is_Palindrome[i][i] = True
            ret = s[i:i+1]
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                is_Palindrome[i][i+1] = True
                ret = s[i:i+2]
        
        for length in range(3, len(s)+1):
            # i: substring starting idx
            for i in range(0, len(s) - length + 1):
                # j: substring last indx
                j = i + length - 1
                if j >= len(s):
                    break
                
                if s[i] == s[j] and is_Palindrome[i+1][j-1]:
                    is_Palindrome[i][j] = True
                    if length > len(ret):
                        ret = s[i:j+1]
                        
        return ret

 

대칭의 특성을 이용한 방법:

전체 string의 모든 문자에 대해 해당 문자가 대칭의 중심이 되는지 여부를 계산한다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def get_Panlindromic_idx(s, idx):
            ret = ''
            l = idx - 1
            r = idx + 1
            while l >= 0 and r < len(s):
                if s[l] != s[r]:
                    break
                l -= 1
                r += 1
            ret = s[l+1:r]
            if idx >= 1 and s[idx-1] == s[idx]:
                l = idx - 2
                r = idx + 1
                while l >= 0 and r < len(s):
                    if s[l] != s[r]:
                        break
                    l -= 1
                    r += 1
                if len(s[l+1:r]) > len(ret):
                    ret = s[l+1:r]
            return ret
        ret = ''
        for idx in range(0, len(s)):
            substr = get_Panlindromic_idx(s, idx)
            if len(substr) > len(ret):
                ret = substr
        return ret