[LeetCode] 5. Longest Palindromic Substring 풀이 및 코드

동적 프로그래밍 카테고리에 있는 문제로 가장 긴 앞뒤가 같은 문자열을 찾는 문제이다. 

풀이

동적 프로그래밍으로 문제를 풀기 위해서는 계산한 결과를 저장하여 다음에 '재사용'하여야 한다. 

Palindrome은 앞뒤가 같은 문자열로, 전체가 palindrome이면 부분도 palindrome이다. "abcba"로 예를 들어보자. "abcba"가 palindrome이면, "bcb", "c"도 모두 palindrome이다.

palindrome

따라서 작은 문제부터 풀고, 큰 문제는 +𝛂만 추가로 확인하면 된다. 우선 가장 가운데의 "c"가 palindrome인지 확인하고, 맞다면 그 양 옆의 문자인 "b"를 추가로 확인한다. 양 옆의 문자가 같다면, 이 또한 palindrome이다. 그러면 다시 그 양 옆의 문자를 확인하는 식으로 문자열의 끝까지 확인한다. 

---

코드

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        lookup_table = [[0 for _ in range(len(s))] for _ in range(len(s)+1)]
        maxLen = 0
        maxStr = ""
        for i in range(len(s)):
            for j in range(i, len(s)):
                if i == 0:
                    lookup_table[i+1][j] = 1
                else:
                    if lookup_table[i-1][j-1] >= 0 and s[j] == s[j-i]:
                        lookup_table[i+1][j] = lookup_table[i-1][j-1]+2
                    else:
                        lookup_table[i+1][j] = -1
                        
                if lookup_table[i+1][j] > maxLen:
                    maxLen = lookup_table[i+1][j]
                    maxStr = s[j-i:j+1]
                    
        return maxStr                         

---

리트코드 제출 결과

---

참조

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