5. 最长回文子串

题目

• 题号：5
• 难度：中等
• https://leetcode-cn.com/problems/longest-palindromic-substring/

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

示例1

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

实现

思路1 暴力匹配

• 枚举所有长度大于等于 22 的子串，依次判断它们是否是回文
• 具体实现时，可以只针对大于“当前得到的最长回文子串长度”的子串进行“回文验证”

• 在记录最长回文子串时，只记录“当前子串的起始位置”和“子串长度”，不必做截取。节省空间。

  class Solution:
    # 暴力匹配（超时）
    def longestPalindrome(self, s: str) -> str:
        # 特判
        size = len(s)
        if size < 2:
            return s
  
        max_len = 1
        res = s[0]
  
        # 枚举所有长度大于等于 2 的子串
        for i in range(size - 1):
            for j in range(i + 1, size):
                if j - i + 1 > max_len and self.__valid(s, i, j):
                    max_len = j - i + 1
                    res = s[i:j + 1]
        return res
  
    def __valid(self, s, left, right):
        # 验证子串 s[left, right] 是否为回文串
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
  

  思路2 动态规划

  因为回文串具有天然的状态转移，即对于一个长度大于2的回文串，去掉它首尾的两个字母后依然是个回文串。
  根据这样的思路我们可以用表示字符串 s 的第 i 到第 j 个字母组成的串是否为回文串

• 状态： dp[i][j] 表示字串 s[i:j] 是否为回文子串

• 状态转移方程：dp[i][j] = (s[i] == s[j]) and (j - i < 3 or dp[i+1][j-1]) ，所以dp[i][j]参考它左下方的值
• 边界条件：，即
• 初始化：dp[i][i] = true，但实际计算中对角线上的值并不会被参考
• 输出：在得到一个状态的值为true的时候，记录起始位置和长度，等填表全部完成以后再截取

• 答案：所有dp[i][j] = true中 j - i + 1（即字串长度）的最大值。

  class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
  
        if length < 2:
            return s  # 特殊边界
  
        dp = [[False] * length for _ in range(length)]
        max_len = 1
        start = 0
  
        # 这个初始化后面并不会用到
        # for i in range(size):
        #     dp[i][i] = True
  
        for j in range(1, length):
            for i in range(0, j):
                # 动态转移方程
                if s[i] != s[j]:
                    dp[i][j] == False
                else:
                    if j-i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i+1][j-1]
  
                # 更新 max_len和start记录
                if dp[i][j]:
                    cur_len = j - i + 1
                    if cur_len > max_len:
                        max_len = cur_len
                        start = i 
  
        # 填表全部结束后再截取
        return s[start : start+max_len]
  

  时间复杂度：，其中n是字符串的长度。因为状态总数为，对于每个状态我们需要转移的时间为
  空间复杂度：，即存储状态需要的空间