0072. Edit Distance¶
题目信息¶
- 题号:
编辑距离
- 难度:
Medium
- 主题:
字符串、动态规划、状态压缩
- 原题:
- 重点:
从枚举编辑序列,推导到前缀最优状态,再压缩为一行
题目重述¶
给定两个字符串 word1 和 word2,允许对 word1 重复执行以下操作:
插入一个字符;
删除一个字符;
替换一个字符。
返回把 word1 转换成 word2 所需的最少操作次数。
字符串长度可以为 0,最大为 500;字符串只包含小写英文字母。
自建示例¶
输入:word1 = "abc", word2 = "yabd"
输出:2
先在开头插入 y,再把 c 替换为 d。
输入:word1 = "stone", word2 = "money"
输出:4
可以删除 s 和 t 得到 one,再在首尾分别插入 m 和 y。
输入:word1 = "", word2 = "code"
输出:4
空串只能连续插入四个字符才能得到目标字符串。
C++ 实现¶
#include <algorithm>
#include <string>
#include <vector>
class Solution {
private:
int plainRecursion(
const std::string& source,
const std::string& target,
int sourceLength,
int targetLength
) {
if (sourceLength == 0) {
return targetLength;
}
if (targetLength == 0) {
return sourceLength;
}
if (source[sourceLength - 1] == target[targetLength - 1]) {
return plainRecursion(
source,
target,
sourceLength - 1,
targetLength - 1
);
}
int replaceCost = plainRecursion(
source,
target,
sourceLength - 1,
targetLength - 1
);
int deleteCost = plainRecursion(
source,
target,
sourceLength - 1,
targetLength
);
int insertCost = plainRecursion(
source,
target,
sourceLength,
targetLength - 1
);
return 1 + std::min({replaceCost, deleteCost, insertCost});
}
int memoDfs(
const std::string& source,
const std::string& target,
int sourceLength,
int targetLength,
std::vector<std::vector<int>>& memo
) {
if (sourceLength == 0) {
return targetLength;
}
if (targetLength == 0) {
return sourceLength;
}
int& cached = memo[sourceLength][targetLength];
if (cached != -1) {
return cached;
}
if (source[sourceLength - 1] == target[targetLength - 1]) {
cached = memoDfs(
source,
target,
sourceLength - 1,
targetLength - 1,
memo
);
return cached;
}
int replaceCost = memoDfs(
source,
target,
sourceLength - 1,
targetLength - 1,
memo
);
int deleteCost = memoDfs(
source,
target,
sourceLength - 1,
targetLength,
memo
);
int insertCost = memoDfs(
source,
target,
sourceLength,
targetLength - 1,
memo
);
cached = 1 + std::min({replaceCost, deleteCost, insertCost});
return cached;
}
int memoizedDistance(
const std::string& source,
const std::string& target
) {
int sourceLength = static_cast<int>(source.size());
int targetLength = static_cast<int>(target.size());
std::vector<std::vector<int>> memo(
sourceLength + 1,
std::vector<int>(targetLength + 1, -1)
);
return memoDfs(
source,
target,
sourceLength,
targetLength,
memo
);
}
int tableDp(
const std::string& source,
const std::string& target
) {
int sourceLength = static_cast<int>(source.size());
int targetLength = static_cast<int>(target.size());
std::vector<std::vector<int>> dp(
sourceLength + 1,
std::vector<int>(targetLength + 1)
);
for (int i = 0; i <= sourceLength; ++i) {
dp[i][0] = i;
}
for (int j = 0; j <= targetLength; ++j) {
dp[0][j] = j;
}
for (int i = 1; i <= sourceLength; ++i) {
for (int j = 1; j <= targetLength; ++j) {
if (source[i - 1] == target[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
continue;
}
int replaceCost = dp[i - 1][j - 1];
int deleteCost = dp[i - 1][j];
int insertCost = dp[i][j - 1];
dp[i][j] = 1 + std::min({
replaceCost,
deleteCost,
insertCost
});
}
}
return dp[sourceLength][targetLength];
}
int rollingDp(
const std::string& source,
const std::string& target
) {
if (target.size() > source.size()) {
return rollingDp(target, source);
}
int sourceLength = static_cast<int>(source.size());
int targetLength = static_cast<int>(target.size());
std::vector<int> dp(targetLength + 1);
for (int j = 0; j <= targetLength; ++j) {
dp[j] = j;
}
for (int i = 1; i <= sourceLength; ++i) {
int diagonal = dp[0];
dp[0] = i;
for (int j = 1; j <= targetLength; ++j) {
int up = dp[j];
if (source[i - 1] == target[j - 1]) {
dp[j] = diagonal;
} else {
int replaceCost = diagonal;
int deleteCost = up;
int insertCost = dp[j - 1];
dp[j] = 1 + std::min({
replaceCost,
deleteCost,
insertCost
});
}
diagonal = up;
}
}
return dp[targetLength];
}
public:
int minDistance(std::string word1, std::string word2) {
return rollingDp(word1, word2);
}
};
题解¶
枚举编辑序列¶
从两个字符串的末尾观察。若末字符相同,可以直接匹配它们,继续处理两侧更短的前缀。 末字符不同时,最后一次操作只有三种可能:替换、删除或插入。
朴素递归会分别尝试三种操作。多个操作序列会反复到达相同的前缀长度对,因而产生大量重复计算。
前缀状态¶
定义 dp[i][j] 为把 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。
具体操作历史不会影响剩余问题,前缀长度已经包含转移所需的全部信息。
当一侧前缀为空时,操作数由另一侧长度唯一确定:
dp[i][0] = i 删除 i 个字符
dp[0][j] = j 插入 j 个字符
末操作分类¶
若 word1[i-1] 与 word2[j-1] 相同,末字符无需编辑:
dp[i][j] = dp[i-1][j-1]
若末字符不同,三种操作与旧状态一一对应:
replace: dp[i-1][j-1]
delete: dp[i-1][j]
insert: dp[i][j-1]
dp[i][j] = 1 + min(replace, delete, insert)
替换同时消耗两个末字符;删除只消耗源字符串末字符;插入目标末字符后,只需继续完成当前源前缀到更短目标前缀的转换。
记忆化消除重复¶
递归状态只由 (i,j) 决定,共有 (m+1)(n+1) 个。为每个状态缓存第一次计算的结果后,后续递归直接复用,指数级搜索被压缩为有限状态图。
二维表格¶
每个状态只依赖左上、上方和左方,因此可以按行从左到右填表。计算 dp[i][j] 时,这三个前驱状态都已经完成。
以 "abc" 转换为 "yabd" 为例,状态表为:
"" y a b d
"" 0 1 2 3 4
a 1 1 1 2 3
b 2 2 2 1 2
c 3 3 3 2 2
右下角的 2 对应一次插入和一次替换。
一维滚动¶
逐行更新时,一维数组中的三个值分别表示:
覆盖前的
dp[j]是二维表中的上方状态;更新后的
dp[j-1]是当前行左方状态;diagonal保存覆盖前的左上状态。
当前格计算完成后,把旧上方值交给 diagonal,供下一列使用。完整二维表因此压缩为一行。
较短字符串作为列¶
滚动数组长度由列数决定。编辑距离在交换两个字符串后不变,因此先让较短字符串作为列,可把空间降为
O(min(m,n))。
正确性¶
任意编辑序列的最后一步必然属于匹配、替换、删除或插入之一。删除最后一步后,剩余操作对应一个严格更小的前缀状态;若该前缀不是最优解,就能替换成更短序列并改进原方案。
状态转移枚举了所有可能的最后一步,并对每类取最优值,因此每个 dp[i][j] 都是对应前缀的最少编辑次数。最终状态 dp[m][n] 即为完整字符串的编辑距离。
复杂度¶
设两个字符串长度分别为 m 和 n:
朴素递归为指数级时间,递归深度为
O(m+n);记忆化与二维 DP 的时间、空间均为
O(mn);一维滚动 DP 的时间为
O(mn),空间为O(min(m,n))。