118.编辑距离

题目

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

思路: 动态规划

想象你手上拿着两个字符串，你想知道从word1变到word2的最小部署。

你可以从两个字符串的开头一点点往后看，每次比较当前字符。

关键想法: 把大问题拆成小问题

定义 dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最少操作数。

例如，dp[2][3] 表示把 word1 的前 2 个字符变成 word2 的前 3 个字符的最少步数。

怎么从子问题得到当前问题

当我们考虑word1的第i个字符(word1[i-1])和word2的第j个字符(word2[j-1])时，有三种可能得方式到达当前状态:

如果这两个字符相等: 那么不需要额外操作，直接集成dp[i-1][j-1]的结果。
如果不相等，我们有三种选择，取代价最小的:
- 替换:把 word1[i-1] 替换成 word2[j-1]，然后问题变成 dp[i-1][j-1] + 1。
- 删除：删除 word1[i-1]，然后问题变成 dp[i-1][j] + 1。
- 在 word1 中插入一个等于 word2[j-1] 的字符，然后问题变成 dp[i][j-1] + 1。

状态转移方程

如果 word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
否则:
    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

初始化

dp[0][j] = j：空字符串变成 word2 的前 j 个字符，需要插入 j 次。
dp[i][0] = i：word1 的前 i 个字符变成空字符串，需要删除 i 次。

手动模拟（以 "horse" → "ros" 为例）

我们画一个 6×4 的表格（word1 长度 5，word2 长度 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

填表过程（部分关键）：

dp[1][1]：'h' vs 'r'，不等，取 min(dp[0][0], dp[0][1], dp[1][0]) +1 = min(0,1,1)+1 = 1。
dp[2][2]：'o' vs 'o'，相等，继承 dp[1][1]=1。
dp[3][3]：'r' vs 's'，不等，取 min(dp[2][2]=1, dp[2][3]=2, dp[3][2]=2)+1 = 2。
最终 dp[5][3] = 3。

class Solution {
    fun minDistance(word1: String, word2: String): Int {
        val m = word1.length
        val n = word2.length

        // dp[i][j] 表示 word1 前 i 个字符到 word2 前 j 个字符的最小编辑距离
        val dp = Array(m + 1) { IntArray(n + 1) }

        // 初始化边界
        for (i in 0..m) dp[i][0] = i
        for (j in 0..n) dp[0][j] = j

        // 填充表格
        for (i in 1..m) {
            for (j in 1..n) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] // 字符相等
                } else {
                    dp[i][j] = minOf(
                        dp[i - 1][j - 1], // 替换
                        dp[i - 1][j],     // 删除
                        dp[i][j - 1]      // 插入
                    ) + 1
                }
            }
        }

        return dp[m][n]
    }
}

复杂度

时间复杂度: O(m × n)，需要遍历整个二维表格。
空间复杂度: O(m × n)，使用二维数组。可以优化为一维数组，空间 O(n)，但为了清晰这里给出二维版本。

下一题

邮箱：charon.chui@gmail.com
Good Luck!