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

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