72. 编辑距离
一句话套路替换/删除/插入三格取最小 +1
题目描述
给你两个单词 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')
提示:
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
思路
时间
O(mn)空间
O(mn)状态
dp[i][j] = word1 前 i 个变成 word2 前 j 个的最少操作数。
转移
字符相同 -> 直接继承对角线 dp[i-1][j-1](不需要操作);
不同 -> 三种操作取最小 +1:dp[i-1][j-1] + 1 替换dp[i-1][j] + 1 删除 word1 的最后一个dp[i][j-1] + 1 插入(等价于删 word2 的一个)
边界
dp[i][0] = i(全删)、dp[0][j] = j(全插)。这一行最容易忘。
家族
Q10 正则匹配、Q97 交错字符串、Q583 只能删除(= LCS 的变体)。
图解
字符串
intention(来自本仓库测试数据,下标从 0 开始)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0072 {
class Solution {
public:
int minDistance(const string& a, const string& b) {
const int m = (int)a.size(), n = (int)b.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
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)
dp[i][j] = (a[i - 1] == b[j - 1])
? dp[i - 1][j - 1]
: 1 + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
return dp[m][n];
}
// 一维滚动版:注意 prev 保存的是「上一行左上角」的旧值
static int minDistanceRolling(const string& a, const string& b) {
const int m = (int)a.size(), n = (int)b.size();
vector<int> dp(n + 1);
for (int j = 0; j <= n; ++j) dp[j] = j;
for (int i = 1; i <= m; ++i) {
int diag = dp[0]; // dp[i-1][j-1]
dp[0] = i;
for (int j = 1; j <= n; ++j) {
int old = dp[j]; // 这就是下一轮的 dp[i-1][j-1]
dp[j] = (a[i - 1] == b[j - 1])
? diag
: 1 + min({diag, dp[j], dp[j - 1]}); // 替换 / 删 / 插
diag = old;
}
}
return dp[n];
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0072::Solution s;
CHECK_EQ(s.minDistance("horse", "ros"), 3);
CHECK_EQ(s.minDistanceRolling("horse", "ros"), 3);
CHECK_EQ(s.minDistance("intention", "execution"), 5);
CHECK_EQ(s.minDistanceRolling("intention", "execution"), 5);
CHECK_EQ(s.minDistance("", "abc"), 3);
CHECK_EQ(s.minDistance("abc", ""), 3);
CHECK_EQ(s.minDistance("", ""), 0);
CHECK_EQ(s.minDistance("abc", "abc"), 0);
CHECK_EQ(s.minDistance("ab", "ba"), 2);
CHECK_EQ(s.minDistance("foo", "bar"), 3); // 三位全替换
CHECK_EQ(s.minDistance("abb", "a"), 2); // 删两个
// 二维版与一维滚动版必须在任意输入上一致(互相检验实现正确性)
vector<pair<string, string>> cases{{"horse", "ros"}, {"abcab", "cba"}, {"", "aaaa"},
{"a", "pqrs"}, {"intention", "execution"}, {"ab", "ba"}};
for (const auto& c : cases) CHECK_EQ(s.minDistance(c.first, c.second),
s.minDistanceRolling(c.first, c.second));