跳到主要内容

LeetCode 72. 编辑距离

本节目标

用两个字符串前缀的最少编辑次数统一替换、插入和删除。

这是序列与字符串动态规划中双前缀最小代价的母题。

题意与约束​

允许插入、删除或替换一个字符，求把 word1 变为 word2 的最少操作数。

第一反应与重复子问题​

观察两个前缀的最后字符：相同无需新增代价；不同则最后一次操作必是替换、删除或插入之一。

状态定义与转移推导​

令 dp[i][j] 为前 i 个字符变为前 j 个字符的最少操作数。第一行列为长度；不同时取左上替换、上方删除、左侧插入再加一的最小值。

正确性依据​

最优编辑序列的最后操作只能属于三类，其前一状态分别是对应的更短前缀；取最小代价即覆盖所有合法末步。

样例执行过程​

horse 变为 ros 可替换 h→r 后删除两个字符，总代价 3。

代码实现​

C++17
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        for (int first = 0; first <= static_cast<int>(word1.size()); first++) {
            dp[first][0] = first;
        }
        for (int second = 0; second <= static_cast<int>(word2.size()); second++) {
            dp[0][second] = second;
        }
        for (int first = 1; first <= static_cast<int>(word1.size()); first++) {
            for (int second = 1; second <= static_cast<int>(word2.size()); second++) {
                int replace = dp[first - 1][second - 1] + (word1[first - 1] != word2[second - 1]);
                dp[first][second] = min({replace, dp[first - 1][second] + 1, dp[first][second - 1] + 1});
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

复杂度分析​

时间 O(mn)，二维表空间 O(mn)。

边界与易错点​

  • 空串变为长度 k 的串需要 k 次插入或删除。
  • 字符相同时直接继承左上状态，不应额外加一。

模式迁移​

带权编辑、通配符匹配和 DNA 对齐都可通过扩展操作代价或状态语义演化。