题目

最长回文子串

提示

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

示例 1：

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

示例 2：

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

提示：

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

解题过程

暴力肯定可以解，求出所有子串，然后判断是否是回文，再求出最大值。然后可以在 for 里优化一下，但基本时间复杂度是 O(N^3)。

继续想，每个单个字母的子串都是回文子串，只不过长度为1。然后每个回文子串去掉首尾后仍然是回文子串，比如 aba 去掉首尾 b 仍然是回文子串。于是编写代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func longestPalindrome(input string) string {
    longestPalindrome := input[0:1]
	for i := 0; i < len(input); i++ {
        var start int = i
		var end int = i
        for {
            if start < 0 || end >= len(input) {
                break
            }

            if input[start] != input[end] {
                break
            }

            if len(input[start:end+1]) > len(longestPalindrome) {
                longestPalindrome = input[start : end+1]
            }

            start--
            end++
        }
    }

    return longestPalindrome
}

上面的代码中，以每个字符为中心，向两边扩散，直到不满足回文条件。这样就可以在 O(N^2) 的时间复杂度内求出最长的回文子串。结果发现这样并不能通过全部测试用例，因为对于偶数长度的回文子串，上面的代码无法正确处理，比如 s = "abba"，上面的代码只能以 b 为中心扩散，无法以 bb 为中心扩散。在这里卡住之后，尝试过单独处理偶数长度的回文子串，结果发现代码会变得异常复杂。后面考虑到回文子串有一个特性，就是如果是偶数字符串的话，那中间两个字符必须相等，所以先找出相同字符的最大子串，然后再以这个子串的中点为中心，向两边扩散。这样就可以同时处理奇数和偶数长度的回文子串了。

后面看到也可以在每个字符之间也加一个虚拟字符，这样就可以将奇数和偶数长度的回文子串都处理了，一开始没想到

修改代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

func longestPalindrome(input string) string {
	longestPalindrome := input[0:1]
	for i := 0; i < len(input); i++ {
		var start int = i
		var end int = i

		for {
			if start < 0 {
				break
			}

			if input[start] != input[i] {
				break
			}

			start--
		}
		start++

		for {
			if end >= len(input) {
				break
			}

			if input[end] != input[i] {
				break
			}

			end++
		}
		end--

		for {
			if start < 0 || end >= len(input) {
				break
			}

			if input[start] != input[end] {
				break
			}

			if len(input[start:end+1]) > len(longestPalindrome) {
				longestPalindrome = input[start : end+1]
			}

			start--
			end++
		}
	}

	return longestPalindrome
}

这样已经可以通过所有测试用例了，并且时间复杂度和空间复杂度都不错。后面还有一种写法，运行时间可能会稍慢，但代码更精简，就是分别以奇数字符串和偶数字符串为中心来扩散。这样就可以简化上面的代码逻辑，抽象出一个函数 expandAroundCenter，用来处理以某个中心点向两边扩散的逻辑。这样就可以简化代码，同时也能处理奇数和偶数长度的回文子串。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// longestPalindrome finds the longest palindromic substring in the input string.
func longestPalindrome(input string) string {
    if len(input) == 0 {
        return ""
    }

    longest := input[0:1] // Initialize with the first character

    for center := 0; center < len(input); center++ {
        // Check for odd-length palindromes
        palindrome1 := expandAroundCenter(input, center, center)
        // Check for even-length palindromes
        palindrome2 := expandAroundCenter(input, center, center+1)

        // Update the longest palindrome if a longer one is found
        if len(palindrome1) > len(longest) {
            longest = palindrome1
        }
        if len(palindrome2) > len(longest) {
            longest = palindrome2
        }
    }

    return longest
}

// expandAroundCenter expands around the given center indices and returns the longest palindrome.
func expandAroundCenter(input string, left, right int) string {
    for left >= 0 && right < len(input) && input[left] == input[right] {
        left--
        right++
    }
    // Return the palindrome substring
    return input[left+1 : right]
}

反思

其实细想这题是比较接近于动态规划的思想的，因为回文子串有一个特性，就是去掉首尾仍然是回文子串，这个特性可以用来构建动态规划表格。只不过这题没有使用表格的方式来存储中间结果，而是直接在字符串上进行扩散计算。复盘一下，发现动态规划类的题也是自己很大的一个思维漏洞。通过这题尝试用动态规划的思想来思考。

判断是否是动态规划

首先，要明确动态规划的定义：动态规划是将一个复杂的问题分解成简单的子问题，存储子问题的结果，以避免重复计算。回文子串可以看作是一个典型的动态规划问题，因为它满足最优子结构和无后效性。

  1. 最优子结构：一个回文串去掉首尾仍然是回文串。
  2. 无后效性：如果一个字符串是回文的，那么它的子串也可以通过相同的方法来判断是否为回文。
  3. 重复计算：在暴力解法中，我们会多次计算同一个子串是否为回文，这就是动态规划要避免的。

遇到动态规划的题，可以考虑通过写动态转移方程来帮助自己理清思路。用 来表示字符串 s 从索引 i 到 j 是否是回文子串，用 ture 和 false 来表示真假。那就可以写出动态转移方程：

也就是说要判断 s[i:j] 是否是回文子串，只需要看 s[i+1:j-1] 是否是回文子串，并且 s[i] 和 s[j] 是否相等。

构建动态规划表格

基于上面转移方程，我们可以构建一个二维的 DP 表格来存储中间结果，最终求出最长的回文子串。

i \ j 0 1 2 3 4
0 T F F F F
1 F T F F F
2 F F T F F
3 F F F T F
4 F F F F T

上表中 T 表示 s[i:j] 是回文子串，F 表示不是。我们可以从下往上，从左往右填充这个表格。初始化时，所有的单个字符都是回文子串，所以对角线上的值都是 T。然后根据转移方程填充表格。值得注意的是其中对角线下的值是没有意义的，因为 i 永远不可能大于 j，所以表格中 i > j 的部分可以忽略。

分阶段计算

有了这个表格，接下来就是思考如何分阶段填充表格。这里有一个思维误区，就是先想当然的用两个循环来填充表格，外层循环控制 i，内层循环控制 j，这是还没有理解动态规划的本质，其本质是分阶段，从上面的转移方程也可知，P(i, j) 的值依赖于 P(i+1, j-1) 的值，所以我们应该先填充 P(i+1, j-1)，也就是先填充长度小的子串，再填充长度大的子串。这样才能保证在计算 P(i, j) 时，P(i+1, j-1) 已经被计算过了。
基于上面的分析，我们可以使用两层循环来填充表格，外层循环控制子串的长度，内层循环控制 i 的位置，j 可以通过 i 和子串长度来计算。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func longestPalindrome(s string) string {
    var dp [][]bool = make([][]bool, len(s))
    var longest = s[0:1]

    for i := 0; i < len(s); i++ {
        dp[i] = make([]bool, len(s))
        dp[i][i] = true
    }

    for l := 2; l < len(s); l++ {
        for i := 0; i < len(s)-1; i++ {
            j := i+l-1
            if j >= len(s) {
                break
            }

            if s[i] != s[j] {
                dp[i][j] = false
                continue
            }
        
            if dp[i+1][j-1] {
                dp[i][j] = true

                if l > len(longest) {
                    longest = s[i:j+1]
                }
            }
        }
    }

    return longest
}

部分测试用例无法通过，因为又忽略了一个细节，就是偶数个字符的回文子串，比如 abba 的时候，变化如下：

l=2，i=0，j=1，此时 s[0] 和 s[1] 不相等，所以 dp[0][1] = false
l=2，i=1，j=2，此时 s[1] 和 s[2] 相等，所以 dp[1][2] 应该为 true，然而 if dp[i+1][j-1] 的条件判断会导致 dp[1][2] 无法被正确设置为 true，因为 dp[2][1] 为 false，所以需要单独处理长度为2的情况。
修改代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func longestPalindrome(s string) string {
	var dp [][]bool = make([][]bool, len(s))
	var longest = s[0:1]

	for i := 0; i < len(s); i++ {
		dp[i] = make([]bool, len(s))
		dp[i][i] = true
	}

	for l := 2; l < len(s); l++ {
		for i := 0; i < len(s)-1; i++ {
			j := i + l - 1
			if j >= len(s) {
				break
			}

			if s[i] != s[j] {
				dp[i][j] = false
				continue
			}

			if (j-1)-(i+1) < 0 {
				dp[i][j] = true
			} else {
				dp[i][j] = dp[i+1][j-1]
			}

			if dp[i][j] && l > len(longest) {
				longest = s[i : j+1]
			}
		}
	}

	return longest
}

这里又犯了一个错误，就是在计算 dp[i][j] 的时候，忘记了要考虑长度为2的情况。对于长度为2的回文子串，由于编写的代码 for l := 2; l < len(s); l++ 就会导致跳过长度为2的情况，修改代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func longestPalindrome(s string) string {
	var dp [][]bool = make([][]bool, len(s))
	var longest = s[0:1]

	for i := 0; i < len(s); i++ {
		dp[i] = make([]bool, len(s))
		dp[i][i] = true
	}

	for l := 2; l <= len(s); l++ {
		for i := 0; i < len(s)-1; i++ {
			j := i + l - 1
			if j >= len(s) {
				break
			}

			if s[i] != s[j] {
				dp[i][j] = false
				continue
			}

			if (j-1)-(i+1) < 0 {
				dp[i][j] = true
			} else {
				dp[i][j] = dp[i+1][j-1]
			}

			if dp[i][j] && l >= len(longest) {
				longest = s[i : j+1]
			}
		}
	}

	return longest
}

当然上面单独处理整个字符串长度为2的情况也是可以的，因为对于长度为2的字符串，只要 s[i] == s[j] 就是回文子串。