2026-06-30
#72 二维DP 中等

编辑距离

在 LeetCode 上查看 ↗

📋 题目描述

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。

示例 1

输入：word1 = "horse", word2 = "ros"
输出：3（horse → rorse → rose → ros）

💭 模拟答题者思考

1. 两串问题 → 尝试「前 i 个」和「前 j 个」的子问题定义，自然导向二维 DP。

2. 三种操作的意义：删除=跳过 word1 的字符（i-1, j）；插入=跳过 word2 的字符（i, j-1）；替换=同时消耗两个字符（i-1, j-1）。

3. 字符相等时（word1[i-1]==word2[j-1]）不需要替换，直接继承 dp[i-1][j-1]。

4. 边界：dp[i][0]=i（全删），dp[0][j]=j（全插）。

🧠 变量语义（先读这三句再编码）

变量类型语义（三句法）
dp[i][j]int[][]定义：word1 的前 i 个字符变成 word2 的前 j 个字符的最少操作数
维护：满足最优子结构：dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
更新：按 i/j 递增顺序计算，当 word1[i-1]==word2[j-1] 时 cost=0 否则 cost=1

⌨️ 落码步骤

1. dp[i][0] = i, dp[0][j] = j（边界初始化）

2. 双重循环遍历 i,j，若 word1[i-1]==word2[j-1]：dp[i][j] = dp[i-1][j-1]

3. 否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

4. 返回 dp[m][n]

💻 代码实现 

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        # dp[i][j]：word1 前 i 个 → word2 前 j 个的最少操作数
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1):
            dp[i][0] = i  # 全删
        for j in range(n + 1):
            dp[0][j] = j  # 全插

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = 1 + min(
                        dp[i-1][j],    # 删除 word1[i-1]
                        dp[i][j-1],    # 插入 word2[j-1]
                        dp[i-1][j-1]   # 替换
                    )
        return dp[m][n]

# 空间优化到 O(n)：
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        prev = list(range(n + 1))
        for i in range(1, m + 1):
            cur = [i] + [0] * n
            for j in range(1, n + 1):
                if word1[i-1] == word2[j-1]:
                    cur[j] = prev[j-1]
                else:
                    cur[j] = 1 + min(prev[j], cur[j-1], prev[j-1])
            prev = cur
        return prev[n]
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector> dp(m + 1, vector(n + 1));

        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            }
        }
        return dp[m][n];
    }
};
// 时间 O(mn)，空间 O(mn)，可优化到 O(n)

📈 复杂度分析

时间复杂度 O(mn)
空间复杂度 O(mn) / O(n)

⚠️ 常见坑

❗ 边界初始化：dp[i][0]=i 不是默认的 0——从 word1 到空串需要 i 次删除。

❗ 字符相等时是 dp[i-1][j-1]（无代价），不是 +1 再 min。

❗ 三种操作（删插替）中「插入」对应 dp[i][j-1]，很多人这里搞反。

🔍 必测边界 Case

Case 1：一个为空
word1 = "", word2 = "abc" → 输出 3（全部插入）
Case 2：完全相同
word1 = "abc", word2 = "abc" → 输出 0