[数据结构与算法]LC 5. 最长回文子串（动态规划/中心扩散 - 中等）

LC 5. 最长回文子串

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

? ? ? ? ? 示例 1：? 输入：s = "babad"??输出："bab"或"aba"

? ? ? ? ? 示例 2：? 输入：s = "cbbd"? ?输出："bb"

? ? ? ? ? 示例 3：?输入：s = "a"? ? ? ? ?输出："a"

? ? ? ? ? 示例 4：? 输入：s = "ac"? ? ? ?输出："a"

思路1：动态规划

? ? ? ? 状态含义
? ? ? ? ? ? 可以以子串长度进行遍历 （begin ?end）
? ? ? ? ? ? d[i][j]: 代表以 i 为开头 以 j 为结尾的字符串 是否是回文串 ? 有 0 和 1 两个取值
? ? ? ? 动态方程
? ? ? ? ? ? d[i][j] = d[i+1][j-1] ?当 s[i]=s[j] ? ? ? ? ?i j 之间最少3个元素(加上其本身)?适合长度大于3的子串
? ? ? ? ? ? ? ? ? ? ? ? ? 0 ? ? ? ? ? ?当 s[i]!=s[j]
? ? ? ? 初始化
? ? ? ? ? ? 子串长度为1： 即 i == j 时 ?d[i][j] = 1
? ? ? ? ? ? 子串长度为2： 即 j = i+1 当 s[i]=s[j] ?d[i][j] = 1 ?否则为0?
? ? ? ? ? ? ? ? ? ? ?b ? a ? b ? a ? d
? ? ? ? ? ? ? ? ? ? ?0 ? 1 ? 2 ? 3 ? 4
? ? ? ? ? ? b ? 0 ?1 ? 0
? ? ? ? ? ? a ? 1? ? ? ?1 ? 0
? ? ? ? ? ? b ? 2? ? ? ? ? ? 1 ? 0
? ? ? ? ? ? a ? 3? ? ? ? ? ? ? ? ?1 ? 0
? ? ? ? ? ? d ? 4? ? ? ? ? ? ? ? ? ? ? 1
? ? ? ? 例：
? ? ? ? ? ? ? ? ?b ? a ? b ? a ? d
? ? ? ? ? ? ? ? ?0 ? 1 ? 2 ? 3 ? 4
? ? ? ? b ? 0 ?1 ? 0? ?1? ?0? ?0
? ? ? ? a ? 1? ? ?? 1 ? 0? ?1? ?0
? ? ? ? b ? 2? ? ? ? ? ? 1 ? 0? ?0
? ? ? ? a ? 3? ? ? ? ? ? ? ? ?1 ? 0
? ? ? ? d ? 4? ? ? ? ? ? ? ? ? ? ? 1

复杂度1：时间复杂度O(n^2)? ? 空间复杂度 O(n^2)

PS：该题变形

? ? ? ? ① 最短回文子串，记录最短即可

? ? ? ? ② 输出所有回文子串：二次遍历，所有1对应的start和end代表的子串进行添加到集合中，避免重复。

代码1：

def longestPalindrome2(s):
    n = len(s)
    d = [[0]*n for _ in range(n)]

    # 初始化
    begin, end = 0, 0
    for i in range(n):
        d[i][i] = 1
        if i < n-1 and s[i]==s[i+1]:
            d[i][i+1] = 1
            if 1 > end - begin:
                begin, end = i, i+1
    # i 代表长度  可取值 3 4  5 …… n
    for i in range(3, n+1):
        # j 代表起始位置
        for j in range(n-i+1):
            k = i + j - 1
            if s[j] == s[k]:
                d[j][k] = d[j+1][k-1]
                if k-j > end-begin and d[j+1][k-1] == 1:
                    begin, end = j, k
    return s[begin:end+1]

思路2：中心扩散

? ? ? ? 遍历整个字符串
? ? ? ? ? ? ①对于每个字符串 向两边扩散判断
? ? ? ? ? ? ② 扩散时候分为两种情况
? ? ? ? ? ? ? ? i 长度为 1 的中心 （bab）
? ? ? ? ? ? ? ? ii 长度为 2 的中心 （bb）

代码2：

def findboders(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left, right = left - 1, right + 1
    # while循环完  上边的left和right不符条件  他们的上一组才符合条件
    return left + 1, right - 1

def rewirtelongestPalindrome1(s):
    n = len(s)
    # 遍历整个字符串
    begin, end = 0, 0
    for i in range(n):
        left1, right1 = findboders(s, i, i)
        left2, right2 = findboders(s, i, i+1)
        if right1 - left1 > end - begin:
            begin, end = left1, right1
        if right2 - left2 > end - begin:
            begin, end = left2, right2
    return s[begin:end+1]

复杂度：时间复杂度O(n^2)? ? 空间复杂度 O(n)? ? ?

路虽远，行则将至。事虽难，做则必成?