Leetcode-Medium 5. Longest Palin

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 长度最长为1000。

Example 1:

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

Example 2:

Input: "cbbd"
Output: "bb"

思路

• 假如输入的字符串长度就是1
  那么这个字符串的最长回文串就是它自己，长度就是1
• 假如字符串长度为2，它要是回文串的化，就需要两个字符是相等的。
  即：s[i] == s[j] 且i-j=1(此处假定i是较大索引位置)
• 那么对于i－j>1的情况下呢？是不是只要满足下面的条件就可以了：
  即:s[i] == s[j]&&s[i-1] == s[j+1]
  参考链接：https://juejin.im/post/5aa51c49f265da23870e748d

代码实现

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