Leetcode-Medium 5. Longest Palindromic Substring

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

class Solution(object):
    def longestPalindrome(self, s):
        ans = ''
        max_len = 0
        n = len(s)
        DP = [[False] * n for _ in range(n)]
        # 字符串长度为1
        for i in range(n):
            DP[i][i] = True
            max_len = 1
            ans = s[i]
        # 字符串长度为2
        for i in range(n-1):
            if s[i] == s[i+1]:
                DP[i][i+1] = True
                ans = s[i:i+2]
                max_len = 2
        for j in range(n):
            print(j)
            # 保证s[i]==s[j]，并且s[i]到s[j]是回文字符串
            for i in range(0, j-1):
                print(i)
                if s[i] == s[j] and DP[i+1][j-1]:
                    DP[i][j] = True
                    if max_len < j - i + 1:
                        ans = s[i:j+1]
                        max_len = j - i + 1
        return ans