LC5. 最长回文子串

class Solution:
  def longestPalindrome(self, s: str) -> str:
      # wei哥关于动态规划的题解真的太精彩了，顶礼膜拜
      # https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/
      n = len(s)
      if n < 2:
          return s
      dp = [[False for _ in range(n)] for _ in range(n)]
      for i in range(n):  # 同一个字母自己肯定是回文串
          dp[i][i] = True
      start = 0
      max_len = 1
      # 以横坐标的单词为基准，逐列扫描
      for j in range(1, n):
          for i in range(j):  # range(n)没必要，会超时；用range(j)即可，即检查到j截止
              if s[i] == s[j]:
                  # 如果s[i+1:j-1]中间长度小于2，即该子串总长度为2或3，则该子串肯定是回文子串
                  if j - i < 3:
                      dp[i][j] = True
                  else:  # 否则用递推关系式，当s[i]与s[j]相等时，s[i:j]的状态和s[i+1:j-1]的状态一致
                      dp[i][j] = dp[i + 1][j - 1]
              else:  # 否则若s[i]!=s[j]，记得将dp[i][j]置为False（但是和超时无关）
                  dp[i][j] = False
              if dp[i][j] == True:
                  if j - i + 1 > max_len:
                      max_len = j - i + 1
                      start = i
      return s[start:start + max_len]