最长回文子串

Leetcode Link: 5. 最长回文子串 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一个字符串 s，找到 s 中最长的回文子串。

解法一

思路：滑动窗口的变体 + 对向双指针 遍历字符串的每一个元素，并以每一个元素为中心采用对向双指针，往两边走，对位不等时上一个状态即为一个回文子串

题解：时间 $O(N^2)$, 空间 $O(1)$

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check(l, r):
            nonlocal s, res
            while(1):
	            # 注意越界检查
                if l>=0 and r<len(s) and s[l]==s[r]:
                    l -= 1
                    r += 1
                else:
                    # 说明*上一次*的结果满足要求
                    # 即使刚进来都不满足要求，也可以处理，如 输入 3,4, s[3] != s[4]
                    # 那么此时就不会满足 if 条件，不更新res
                    l = l + 1 
                    r = r - 1
                    if r-l+1 > res[1] - res[0]:
                        res = [l, r+1]
                    break
 
        # 结果
        res = [0,0]
        for l in range(len(s)):
            check(l,l)   # 中心重合
            check(l,l+1) # 中心相邻
        return s[res[0]:res[1]]

解法二

思路：动态规划 这个可能是样本对应模型

动规五步走

1. dp[i][j] 含义：s[i:j+1] 是不是回文子串 (True or False)
2. 递归公式：dp[L][R]=True if s[L]==s[R] and dp[L+1][R-1] is True else False
3. 初始化：对角线为 True，同时相邻两个的位置也要提前初始化，否则需要在主循环中进行判断
4. 遍历顺序：行倒着来，列正常。并且避免已经初始化的位置。
5. 举例 题解：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        res = [0,0] # 记录子串的左右边界（都含）
        for i in range(len(s)):
            dp[i][i] = True
            if i+1<len(s) and s[i]==s[i+1]:
                dp[i][i+1] = True
                res = [i,i+1] # 这里一定记得更新结果，在初始化时如果出现相邻的最大，那当目前为止的最长回文一定是这个
 
        for L in range(len(s)-3, -1, -1): # 注意倒着来，跳过已经初始化的
            for R in range(L+2, len(s)):
                if s[L] == s[R] and dp[L+1][R-1] is True:
                    dp[L][R] = True
                    if R-L+1 > res[1]-res[0]+1:
                        res = [L, R]
        return s[res[0]:res[1]+1]

复习时想用一维dp，dp[i]表示以i位结尾的最长回文子串长度。但是失败了

启发和联系

在动规归中，如果使用dp的含义是[L,R]上的回文子串长度，一定注意需要判断[L+1,R-1]是不是回文子串，即dp[L+1][R-1]>0，然后再+2，如果只判断两者是不是相等就+2，结果会出错，因为你不知道上一个是不是回文就加。