5. Longest Palindromic Substring

5. 最长回文子串

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

1. 动态规划

1.1 状态转移方程

假设$f(i,j)$表示字符串S[i:j]是否为回文串, 那么有:

• 若$f(i+1,j-1)$不是回文, 那么$f(i,j)$不是回文
• 若$f(i+1,j-1)$是回文, 只有当$S[i]==S[j]$时, $f(i,j)$为回文

可以得出: $f(i,j)=f(i+1,j-1) \and (S[i]==S[j]), i+1 < j-1 \implies j-i > 2$

初始值(最小问题解):

• 当有两个字符时, $f(i,i+1) = S[i]==S[i+1]$

迭代法计算过程是一个填表的过程, 以abcba 为例:

i\j	0	1	2	3	4
0	N/A	F (1)	F (5)	F (8)	T (10)
1	N/A	N/A	F (2)	T (6)	F (9)
2	N/A	N/A	N/A	F (3)	F (7)
3	N/A	N/A	N/A	N/A	F (4)
4	N/A	N/A	N/A	N/A	N/A

括号数字代表计算顺序.

1.2 迭代+二维数组

TC: $O(n^2)$ SC: $O(n^2)$

func longestPalindrome(s string) string {
    n := len(s)
    // 动态规划
    dp := make([][]bool, n)
    for i := range dp {
        dp[i] = make([]bool, n)
    }

    start := 0
    maxLen := 1
    for j := 0; j < n; j++ {
        for i := 0; i < j; i++ {
            if j-i > 2 {
                dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
            } else {
                dp[i][j] = s[i] == s[j]
            }

            if dp[i][j] && j-i+1 > maxLen {
                start = i
                maxLen = j-i+1
            }
        }
    }

    return s[start:start+maxLen]
}

1.3 迭代+一维数组

TC: $O(n^2)$ SC: $O(n)$

由上述的计算过程图表可以看到, 二维数组有一半的空间是闲置的, 并且当j-i>2时dp[i][j]只需要用到dp[i+1][j-1].

因此将二维数组映射到i上, 得到一维数组dp[0,..i,..,n], 从计算顺序可以看出, 计算dp[i]后替换掉原来的值并不会影响下一次计算.

func longestPalindrome(s string) string {
    n := len(s)
    // 动态规划
    dp := make([]bool, n)
    
    start := 0
    maxLen := 1
    for j := 0; j < n; j++ {
        for i := 0; i < j; i++ {
            if j-i > 2 {
                dp[i] = dp[i+1] && s[i] == s[j]
            } else {
                dp[i] = s[i] == s[j]
            }

            if dp[i] && j-i+1 > maxLen {
                maxLen = j-i+1
                start = i
            }
        }
    }
    return s[start: start+maxLen]
}

2. 中心扩展

TC: $O(n^2)$ SC: $O(1)$

对于回文:

• 若长度为奇数, 那么其对称中心只有一个字符
• 若长度为偶数, 那么其对称中心是两个相同字符

那么若从对称中心出发, 向两边扩展:

• 若扩展的两个字符相同, 则扩展后是回文, 则继续扩展.
• 若扩展的两个字符不同, 则扩展后不是回文, 停止扩展.

停止扩展后的回文一定是最长的回文, 那么以字符串的每个字符开始扩展就可找出最长回文串.

func longestPalindrome(s string) string {
    n := len(s)

    start, end := 0, 0
    for i := 0; i < n; i++ {
        le1, ri1 := expandCenter(s, i, i)
        le2, ri2 := expandCenter(s, i, i+1)

        if ri1-le1 > end-start {
            start, end = le1, ri1
        }
        if ri2-le2 > end-start {
            start, end = le2, ri2
        }
    }

    return s[start: end+1]
}

func expandCenter(s string, left, right int) (int, int) {
    for left >=0 && right < len(s) && s[left] == s[right] {
        left -= 1
        right += 1
    }

    return left+1, right-1
}

Reference

1. https://leetcode.cn/problems/longest-palindromic-substring/solutions/255195/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/