Adrian Wang's blog

一个完全由AI生成，但是内容高质量的Blog

❌ LeetCode 5 - 最长回文子串：动态规划填表顺序错误分析

Posted on Edited on In , ,
Symbols count in article: 3k Reading time ≈ 3 mins.
详细分析LeetCode第5题“最长回文子串”动态规划解法的常见填表顺序错误，并提供正确的思路与实现。

问题描述

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

示例 1：

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

示例 2：

输入：s = “cbbd”
输出：“bb”

约束条件：

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

错误的解法与分析

一个常见的解决此问题的思路是使用动态规划。我们定义 dp[i][j] 表示字符串 s 中从索引 i 到 j 的子串是否是回文串。

状态转移方程可以这样定义：

  • 如果 s[i] == s[j]：
    • 如果子串长度小于等于 2（即 j - i < 2），那么 dp[i][j] 为 true。
    • 如果子串长度大于 2，那么 dp[i][j] 取决于 dp[i+1][j-1] 是否为回文串。
  • 如果 s[i] != s[j]，那么 dp[i][j] 为 false。

以下是一个尝试实现该思路的 Go 代码，但它存在一个关键的错误：

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 {
	n := len(s)
	if n == 1 {
		return s
	}
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	maxLen := 1
	start := 0
	end := 1 // ❌ 错误点：end 初始化不当，可能导致长度为1时出错
	for i := range s {
		dp[i][i] = true
	}

	// ❌ 错误点：填表顺序问题
	// 当计算 dp[i][j] 时，dp[i+1][j-1] 可能尚未被计算
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if j-i < 2 { // 子串长度为2
				dp[i][j] = s[i] == s[j]
			} else { // 子串长度大于2
				dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
			}
			if dp[i][j] && j-i+1 > maxLen {
				maxLen = j - i + 1
				start = i
				end = j
			}
		}
	}

	return s[start : end+1]
}

错误原因分析

主要的错误在于 DP 表的填充顺序。

在上述代码中，外层循环 i 从 0 遍历到 n-1，内层循环 j 从 i+1 遍历到 n-1。当我们计算 dp[i][j] 时，它依赖于 dp[i+1][j-1] 的值。

让我们考虑一个例子，比如计算 dp[0][3]。根据状态转移方程，它依赖于 dp[1][2]。
在当前的遍历顺序下：

  • i = 0:
    • j = 1: 计算 dp[0][1]
    • j = 2: 计算 dp[0][2] (依赖 dp[1][1])
    • j = 3: 计算 dp[0][3] (依赖 dp[1][2])

当 i=0, j=3 时，我们需要 dp[1][2] 的值。但是，dp[1][2] 会在 i=1, j=2 时才被计算。这意味着在计算 dp[0][3] 时，dp[1][2] 还没有被正确计算出来（其值仍为默认的 false），从而导致 dp[0][3] 的计算错误。

此外，end 变量的初始化为 1，当字符串长度为 1 时，如果 maxLen 没有更新（例如字符串本身就是单个字符，已经是回文），s[start : end+1] 会变成 s[0:2]，这会导致数组越界。对于长度为 1 的字符串，start应为0，end应为0。

正确的解法与思路

为了解决填表顺序的问题，我们需要确保在计算 dp[i][j] 时，其依赖的 dp[i+1][j-1] 已经被计算过。这可以通过改变循环的遍历顺序来实现。

正确的思路是：

  1. 外层循环 i 从 n-1 向下遍历到 0。
  2. 内层循环 j 从 i+1 向上遍历到 n-1。

这样，当我们计算 dp[i][j] 时：

  • i 的值比 i+1 小。
  • j 的值比 j-1 大。
    由于 i 是从大到小遍历的，当计算 dp[i][...] 时，所有 dp[i+1][...] 的行都已经被计算完毕。因此，dp[i+1][j-1] 的值是已知的。

同时，对于 end 的初始化，当 maxLen 为 1 时，start 和 end 都应该是 0（或者说，子串就是 s[0:1]）。

正确的 Go 代码实现

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
func longestPalindrome(s string) string {
	n := len(s)
	if n < 2 { // 处理空字符串或单字符字符串的情况
		return s
	}
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	maxLen := 1
	start := 0
	// end 不需要单独初始化为1，通过dp[i][i] 和后续更新来确定

	// 所有长度为1的子串都是回文串
	for i := 0; i < n; i++ {
		dp[i][i] = true
	}

	// 从后往前遍历 i，确保 dp[i+1][j-1] 已被计算
	for i := n - 1; i >= 0; i-- {
		// 从 i+1 开始遍历 j
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				// 如果子串长度为2 (j-i == 1) 或者内部子串 dp[i+1][j-1] 是回文
				if j-i < 2 || dp[i+1][j-1] {
					dp[i][j] = true
					if j-i+1 > maxLen {
						maxLen = j - i + 1
						start = i
						// end = j // end 可以不在这里更新，最后通过 start 和 maxLen 计算
					}
				}
			}
		}
	}
    // 通过 start 和 maxLen 来确定最终的子串
	return s[start : start+maxLen]
}

在这个修正后的版本中：

  1. i 从 n-1 递减到 0。
  2. j 从 i+1 递增到 n-1。
  3. 简化了 dp[i][j] 的判断逻辑：如果 s[i] == s[j]，那么当子串长度为 2 (j-i == 1，等价于 j-i < 2) 或者内部子串 dp[i+1][j-1] 为回文时，dp[i][j] 才为 true。
  4. end 的更新被移除了，最后直接通过 start 和 maxLen 来截取子串，这样更简洁且不易出错。对于 maxLen 初始化为 1，start 初始化为 0，如果循环没有找到更长的回文串，会返回 s[0:1]，这是正确的。
  5. 处理了 n < 2 的边界情况。

学习总结

动态规划问题的核心之一在于确定正确的状态转移顺序。当一个状态 dp[i][j] 依赖于其他状态时（如本例中的 dp[i+1][j-1]），必须确保在计算当前状态之前，所有依赖的状态都已经被正确计算。

对于二维 DP 表，常见的遍历顺序有：

  • 从上到下，从左到右。
  • 从下到上，从左到右。
  • 从上到下，从右到左。
  • 从下到上，从右到左。

选择哪种顺序取决于状态之间的依赖关系。在本题中，由于 dp[i][j] 依赖于 dp[i+1][j-1]（即左下方的单元格），因此从下往上（i 递减）、从左往右（j 递增，且 j > i）的遍历顺序是合适的。

另外，初始化边界条件和最终结果的提取方式也需要仔细考虑，以避免数组越界或逻辑错误。