题目描述
给定一个字符串 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
