0072. Edit Distance
===================
题目信息
--------
:题号: 0072. 编辑距离
:难度: Medium
:主题: 字符串、动态规划、状态压缩
:原题: `LeetCode 0072 `_
:重点: 从枚举编辑序列,推导到前缀最优状态,再压缩为一行
题目重述
--------
给定两个字符串 ``word1`` 和 ``word2``,允许对 ``word1`` 重复执行以下操作:
* 插入一个字符;
* 删除一个字符;
* 替换一个字符。
返回把 ``word1`` 转换成 ``word2`` 所需的最少操作次数。
字符串长度可以为 0,最大为 500;字符串只包含小写英文字母。
自建示例
--------
.. code-block:: text
输入:word1 = "abc", word2 = "yabd"
输出:2
先在开头插入 ``y``,再把 ``c`` 替换为 ``d``。
.. code-block:: text
输入:word1 = "stone", word2 = "money"
输出:4
可以删除 ``s`` 和 ``t`` 得到 ``one``,再在首尾分别插入 ``m`` 和 ``y``。
.. code-block:: text
输入:word1 = "", word2 = "code"
输出:4
空串只能连续插入四个字符才能得到目标字符串。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
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>& 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(source.size());
int targetLength = static_cast(target.size());
std::vector> memo(
sourceLength + 1,
std::vector(targetLength + 1, -1)
);
return memoDfs(
source,
target,
sourceLength,
targetLength,
memo
);
}
int tableDp(
const std::string& source,
const std::string& target
) {
int sourceLength = static_cast(source.size());
int targetLength = static_cast(target.size());
std::vector> dp(
sourceLength + 1,
std::vector(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(source.size());
int targetLength = static_cast(target.size());
std::vector 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`` 个字符所需的最少操作数。
具体操作历史不会影响剩余问题,前缀长度已经包含转移所需的全部信息。
当一侧前缀为空时,操作数由另一侧长度唯一确定:
.. code-block:: text
dp[i][0] = i 删除 i 个字符
dp[0][j] = j 插入 j 个字符
末操作分类
~~~~~~~~~~
若 ``word1[i-1]`` 与 ``word2[j-1]`` 相同,末字符无需编辑:
.. code-block:: text
dp[i][j] = dp[i-1][j-1]
若末字符不同,三种操作与旧状态一一对应:
.. code-block:: text
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"`` 为例,状态表为:
.. code-block:: text
"" 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))``。