algorithms►leetcode

002-最长回文子串（DP）

最长回文子串

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

示例 1：

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

示例 2：

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

提示：

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

Solution

复杂度分析

  • 时间复杂度：O(n²)，其中n是字符串的长度
  • 空间复杂度：O(1)
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
function longestPalindrome(s) {
    if (!s || s.length === 0) return "";
    
    let start = 0;
    let end = 0;
    
    for (let i = 0; i < s.length; i++) {
        const len1 = expandAroundCenter(s, i, i);      // 奇数长度回文
        const len2 = expandAroundCenter(s, i, i + 1);  // 偶数长度回文
        const maxLen = Math.max(len1, len2);
        
        if (maxLen > end - start) {
            start = i - Math.floor((maxLen - 1) / 2);
            end = i + Math.floor(maxLen / 2);
        }
    }
    
    return s.substring(start, end + 1);
}

function expandAroundCenter(s, left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}
ight++;
}
return right - left - 1;
}

用最简单的方式理解动态规划解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function findLength(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    // 创建DP表，多一行一列方便处理边界条件
    const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
    let maxLen = 0;
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 如果当前元素相同，则长度为左上角值+1
            if (nums1[i-1] === nums2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                maxLen = Math.max(maxLen, dp[i][j]);
            }
            // 不同时保持0（因为是子数组，不是子序列）
        }
    }
    
    return maxLen;
}

让我用最直白的方式重新解释这个动态规划解法，保证你能看懂！

举个生活中的例子

想象你有两条珠子串（数组），你要找出两条珠串中连续相同珠子排列的最长一段。

比如：

  • 珠串A：红-蓝-绿-蓝-红
  • 珠串B：绿-蓝-红-黄-紫

最长的相同连续排列是”绿-蓝-红”，长度为3。

动态规划表格的直观理解

我们创建一个表格，行代表珠串A的每个珠子，列代表珠串B的每个珠子。表格每个格子记录的是：以这两个珠子结尾的相同连续排列的长度。

初始表格（第一行和第一列都是0）：

绿 蓝 红 黄 紫
0 0 0 0 0 0
红 0
蓝 0
绿 0
蓝 0
红 0

填表规则（超级重要！）

规则：只有当两个珠子相同时才填数字，数字 = 左上角格子的数字 + 1

  1. 比较红(珠串A)和绿(珠串B) → 不同 → 填0
  2. 比较红和蓝 → 不同 → 填0
  3. 比较红和红 → 相同 → 看左上角是0 → 填0+1=1
  4. 比较蓝和绿 → 不同 → 填0
  5. 比较蓝和蓝 → 相同 → 左上角是0 → 填0+1=1
  6. 比较绿和绿 → 相同 → 左上角是0 → 填0+1=1
  7. 比较蓝和蓝 → 相同 → 左上角是1 → 填1+1=2
  8. 比较红和红 → 相同 → 左上角是2 → 填2+1=3

填完后的表格：

绿 蓝 红 黄 紫
0 0 0 0 0 0
红 0 0 0 1 0 0
蓝 0 0 1 0 0 0
绿 0 1 0 0 0 0
蓝 0 0 2 0 0 0
红 0 0 0 3 0 0

为什么这样填表？

因为我们要找的是连续的相同排列：

  • 当两个珠子相同时，说明可以延续前面的相同排列
  • 数字表示”当前连续相同的长度”
  • 左上角的数字表示”不算当前珠子时的长度”

找出最大值

扫描整个表格，最大的数字是3，这就是我们要找的最长长度。

对应的相同排列：

  • 从数字3倒推：红(珠串A)和红(珠串B) → 蓝和蓝 → 绿和绿
  • 所以是”绿-蓝-红”

代码对应关系

1
2
3
4
5
if (nums1[i-1] === nums2[j-1]) {
    dp[i][j] = dp[i-1][j-1] + 1; // 左上角值+1
    maxLen = Math.max(maxLen, dp[i][j]); // 更新最大值
}
// 不同时默认为0

总结记忆口诀

  1. 建表格，行列各加1（方便计算）
  2. 相同就取左上+1
  3. 不同就写0
  4. 随时记录最大值
  5. 最后返回最大值

这样理解是不是清楚多了？动态规划其实就是用表格记录中间结果，避免重复计算！