定义

编辑距离（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()];
	}
};