定义

编辑距离(Edit Distance),又称 Levenshtein 距离。

编辑距离是指两个字符串之间,由一个字符串转化为另一个字符串所需的最小编辑操作次数。

许可的编辑操作包括:

  • 在原串中添加一个字符
  • 在原串中删除一个字符
  • 在原串中修改一个字符

解法

解法当然是 DP 了!

先来看看操作,设原串为 A 新串为 B,A 串的长度为 n,B 串的长度为 m,那么现在就有对两个串的 6 种操作。

然而我们可以把操作简化为三种:

  • 在 A 中添加一个字符(等价于在 B 中删除一个字符)
  • 在 B 中添加一个字符(等价于在 A 中删除一个字符)
  • 在 A 中修改一个字符(等价于在 B 中修改一个字符)

然后看看转移,这里用 dp[i][j] 表示 A 从头开始的 i 个字符与 B 从头开始的 j 个字符。

i 和 j 为 0 的时候就表示空串。所以这个二维数组应该开到 dp[n + 1][m + 1]

对于 dp[i][j] 可以由下面三种方式转移得到:

  • dp[i - 1][j] + 1 只需要在现有 A 串的末尾添加一个字符即可

  • dp[i][j - 1] + 1 只需要在现有 B 串的末尾添加一个字符即可

  • dp[i - 1][j - 1] + (A[i - 1] == B[i - 1] ? 0 : 1) 这里需要判断 A 串中第 i 个字符(下标 i - 1)和 B 串中第 j 个字符(下标 j - 1)是否相同。相同的话直接转移,不同的话需要把 A[i - 1] 修改为 B[j - 1],因此编辑距离增加 1

因此 dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i][j] + (A[i - 1] == B[i - 1] ? 0 : 1))

最后看看边界条件,由于空串到任意一个串只需要不断加加加,一个串到空串只需要不断减减减,所以:

  • dp[i][0] = i 在 B 中添加 i 个字符
  • dp[0][j] = j 在 A 中添加 j 个字符

条件齐了,将 i 和 j 从 0 推到 n 和 m 即可,正推时所有前置条件都已经算完了。

时空复杂度均为 O(nm)。


实现

Leetcode 72 编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
public:
int minDistance(string word1, string word2)
{
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));

for (auto i = 0; i < dp.size(); i++) dp[i][0] = i;
for (auto j = 0; j < dp[0].size(); j++) dp[0][j] = j;

for (auto i = 1; i < dp.size(); i++)
for (auto j = 1; j < dp[0].size(); j++)
dp[i][j] = min({
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + (word1[i - 1] == word2[j - 1] ? 0 : 1)
});

return dp[word1.size()][word2.size()];
}
};