[LeetCode] 5 | Longest Palindromic Substring | Python

---

문제 링크: https://leetcode.com/problems/longest-palindromic-substring/

---

문제

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

---

조건

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

---

내 풀이

Palindrome인 'abcba' 안에 속해있는 'bcb'도 palindrome이기 때문에 DP로 풀 수 있다.

한 글자짜리 string은 항상 palindrome이고, 같은 문자가 연속된 두 글자짜리 string('aa' or 'bb')도 palindrome이라는 점에서 시작한다.

---

코드

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