algorithms►leetcode

001-编辑距离（DP）

1. 什么是编辑距离？

编辑距离是衡量两个字符串相似程度的重要指标，表示将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数（插入、删除或替换）

想象你有两个单词：

  • 原单词：”horse”
  • 目标单词：”ros”

编辑距离就是把”horse”变成”ros”最少需要几步操作。允许的操作有三种：

  1. 插入一个字符（比如插入’s’）
  2. 删除一个字符（比如删除’h’）
  3. 替换一个字符（比如把’h’换成’r’）

动态规划解法

基本思路

我们使用一个二维数组 dp 来存储子问题的解，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作次数。

JavaScript 实现

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
function minDistance(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    
    // 创建DP表 (m+1) x (n+1)
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    
    // 初始化边界条件
    for (let i = 0; i <= m; i++) {
        dp[i][0] = i; // 将word1前i个字符变为空串需要i次删除
    }
    for (let j = 0; j <= n; j++) {
        dp[0][j] = j; // 将空串变为word2前j个字符需要j次插入
    }
    
    // 填充DP表
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // 字符相同，无需操作
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,     // 删除word1[i]
                    dp[i][j - 1] + 1,     // 插入word2[j]
                    dp[i - 1][j - 1] + 1 // 替换word1[i]为word2[j]
                );
            }
        }
    }
    
    return dp[m][n];
}

2. 最直观的解法演示

让我们手动计算把”horse”变成”ros”的步骤：

方法一：

  1. horse → rorse （把h替换成r）
  2. rorse → rose （删除第二个r）
  3. rose → ros （删除e）
    总共：3步

方法二：

  1. horse → orse （删除h）
  2. orse → rse （把o替换成r）
  3. rse → ros （把s替换成o，e替换成s）
    总共：4步

显然第一种方法更好，编辑距离就是最小的3。

3. 为什么需要动态规划？

手动计算简单，但计算机需要系统的方法。动态规划就是：

  • 把大问题拆成小问题
  • 记录已经解决的子问题
  • 避免重复计算

4. DP表格超详细构建（以”horse”和”ros”为例）

我们建立一个表格，行是”horse”+空字符，列是”ros”+空字符：

    '' r o s
'' [ , , , ]
h  [ , , , ]
o  [ , , , ]
r  [ , , , ]
s  [ , , , ]
e  [ , , , ]

第一步：初始化边界

第一行：空字符串变成”ros”各阶段需要多少步？

  • ‘’→’’：0步
  • ‘’→’r’：插入r（1步）
  • ‘’→’ro’：插入r+o（2步）
  • ‘’→’ros’：插入r+o+s（3步）

第一列：”horse”各阶段变成空字符串需要多少步？

  • ‘’→’’：0步
  • ‘h’→’’：删除h（1步）
  • ‘ho’→’’：删除h+o（2步）
  • …
  • ‘horse’→’’：删除h+o+r+s+e（5步）

填入后表格：

    '' r o s
'' [0,1,2,3]
h  [1, , , ]
o  [2, , , ]
r  [3, , , ]
s  [4, , , ]
e  [5, , , ]

第二步：填充其他格子

规则：

  1. 如果当前字符相同：取左上角的值（因为不需要操作）
  2. 如果不同：取左、上、左上三个值中的最小值+1

让我们填充几个关键格子：

(1,1)位置：’h’→’r’

  • 字符’h’≠’r’
  • 看：
    • 左：’’→’r’=1（插入）
    • 上：’h’→’’=1（删除）
    • 左上：’’→’’=0（替换）
  • 最小值0+1=1
  • 所以dp[1][1]=1（表示’h’→’r’最少需要1步：替换）

(2,2)位置：’ho’→’ro’

  • 最后一个字符’o’==’o’
  • 直接取左上角的值dp[1][1]=1
  • 因为最后一个字符相同，不需要额外操作

(5,3)位置：’horse’→’ros’

  • 最后一个字符’e’≠’s’
  • 看：
    • 左：’hors’→’ros’=3（插入’s’）
    • 上：’horse’→’ro’=4（删除’e’）
    • 左上：’hors’→’ro’=2（替换’e’→’s’）
  • 最小值2+1=3

最终完整表格：

    '' r o s
'' [0,1,2,3]
h  [1,1,2,3]
o  [2,2,1,2]
r  [3,2,2,2]
s  [4,3,3,2]
e  [5,4,4,3]

右下角的3就是最终答案！

5. 为什么这样计算？

每个格子都代表一个子问题的最优解：

  • 从左来：相当于插入当前列对应的字符
  • 从上来：相当于删除当前行对应的字符
  • 从左上角来：相当于替换（如果不同）或保留（如果相同）

6. 代码逐步对应

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function minDistance(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = Array(m+1).fill().map(() => Array(n+1).fill(0));
    
    // 初始化第一行和第一列
    for(let i=0; i<=m; i++) dp[i][0] = i; // 删除i次
    for(let j=0; j<=n; j++) dp[0][j] = j; // 插入j次
    
    for(let i=1; i<=m; i++) {
        for(let j=1; j<=n; j++) {
            if(word1[i-1] === word2[j-1]) {
                dp[i][j] = dp[i-1][j-1]; // 字符相同，直接继承
            } else {
                dp[i][j] = Math.min(
                    dp[i-1][j] + 1,   // 删除word1[i]
                    dp[i][j-1] + 1,   // 插入word2[j]
                    dp[i-1][j-1] + 1 // 替换
                );
            }
        }
    }
    return dp[m][n]; // 右下角的值就是结果
}

7. 常见疑问解答

Q：为什么表格要比字符串长度多1？
A：因为要考虑空字符串的情况，这是动态规划的边界条件。

Q：如何知道具体进行了哪些操作？
A：可以反向追踪dp表：

  1. 从右下角开始
  2. 比较当前值与左、上、左上值
  3. 找到使当前值产生的路径

Q：时间复杂度能优化吗？
A：空间可以优化到O(n)（只用两行），但时间必须O(m*n)，因为要填满整个表格。

8. 实战练习

试试计算”intention”和”execution”的编辑距离：

  • 先建一个9x9的表格（包括空字符串）
  • 按照上述规则填充
  • 你会发现答案是5

通过这样一步步拆解，你应该对编辑距离有了更直观的理解。动态规划的关键就是找到子问题之间的关系，并用表格记录下来避免重复计算。

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. 最后返回最大值

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