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

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：

输入: “cbbd”
输出: “bb”

解法一：DP

dp[i][j]存放s[i:j+1]是否为回文。dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]，及一个长度为l子串的由其中间l - 2长度的子串加上首位两个字母决定。因此按l由短至长构建dp。当l == 1 or 2时，需要特殊处理。l = 1时一定是True，l ==2时必须两个字母相同才可以。
这个方法时间复杂度为O(N)，因为需要构造dp，构造结果为一个右上三角矩阵。

  1. class Solution:
  2.     def longestPalindrome(self, s: str) -> str:
  3.         ans = ''
  4.         dp = [[False] * len(s) for _ in range(len(s))]
  5.         for l in range(1, len(s) + 1):
  6.             for i in range(len(s) - l + 1):
  7.                 j = i + l - 1
  8.                 if l == 1:
  9.                     dp[i][j] = True
  10.                 elif l == 2:
  11.                     dp[i][j] = s[i] == s[j]
  12.                 else:
  13.                     dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]
  14.                 if dp[i][j] and (l > len(ans)):
  15.                     ans = s[i:j+1]
  16.         return ans

注意！dp的初始化千万不能写成dp = [[False] * len(s)] * len(s)，因为这样生成的行与行之间是浅拷贝！对可变对象做乘法运算要特别小心，返回的对象列表里都是同一个对象的浅拷贝。

解法二：中心扩散法

TODO

解法三：马拉车法

TODO