[Leetcode/파이썬] 5. Longest Palindromic Substring

Longest Palindromic Substring

---

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        left = right = 0

        for i in range(len(s)) :
            odd = self.palindrome(s, i, i)
            even = self.palindrome(s, i, i + 1)
            max_length = max(odd, even)

            if max_length > right - left :
                left = i - (max_length - 1) // 2
                right = i + max_length // 2

        return s[left:right+1]

    def palindrome(self, s, left, right) :
        while 0 <= left and right < len(s) and s[left] == s[right] :
            left -= 1
            right += 1
        return (right - 1) - (left + 1) + 1

첫 번째 풀이는 투포인터를 활용한 풀이이다. 

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        ans = [0, 0]
        
        for i in range(n):
            dp[i][i] = 1
        
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = 1
                ans = [i, i + 1]

        for diff in range(2, n):
            for i in range(n - diff):
                j = i + diff
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = 1
                    ans = [i, j]

        i, j = ans
        return s[i:j + 1]

두 번째 풀이는 다이나믹 프로그래밍을 활용한 풀이이다.