72. 编辑距离

难度：🟡 Medium | 标签：动归 | 状态：⬜ LeetCode 链接

思路

dp[i][j] = 把 word1[0..i) 变成 word2[0..j) 的最小操作数。

• 字符相等 → dp[i-1][j-1]
• 不等 → 1 + min(dp[i-1][j-1] 替换, dp[i-1][j] 删除, dp[i][j-1] 插入)

Base：dp[i][0] = i、dp[0][j] = j。

代码

class Solution {
public:
    int minDistance(string a, string b) {
        int m = a.size(), n = b.size();
        vector<vector<int>> dp(m + 1, vector<int>(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 (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = 1 + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
            }
        return dp[m][n];
    }
};

复杂度

• 时间 O(m · n)，空间 O(m · n)

易错 / 回顾

• 三种操作对应三个前驱：替换 / 删除 / 插入
• base 行列分别是 i 和 j（全删 / 全插）
• 滚动数组：维护两行或一行 + 一变量