72. Edit Distance(困难，确实挺难的，但很经典，双序列DP问题)

时间：2022-08-06 04:49:43

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character

b) Delete a character

c) Replace a character

听人家说，这是 双序列DP问题. 确实，对我来说，这个题的解法好难理解，即使之前做出了几个dp问题．我怎么可能说自己笨呢!

四个优秀的解释：

http://www.stanford.edu/class/cs124/lec/med.pdf

http://www.cnblogs.com/pandora/archive/2009/12/20/levenshtein_distance.html

http://www.jianshu.com/p/39115986db5a

http://www.dreamxu.com/books/dsa/dp/edit-distance.html

一个分治、dp、贪心的优秀小 book：

http://www.dreamxu.com/books/dsa/dc/subset.html

看了人家很多解释，还是自己想出个例子，自己再顺一遍才能较好的理解．Come on!

假设有 3 种操作：

插入，删除 和 修改．假设它们的 cost 均为 1;

注意有的题目可能它们的 cost 不相同, 比如:

  • The costs of both insertion(插入) and deletion(删除) are same value, that is 1;
  • The cost of substitution(替换) is 2．

咱自己的例子：

说例子前需说明什么是 dp[i, j].

dp[i, j] 称为 s1[0..i] 串到 s2[0..j] 的最小距离． 表示 字符串 s1[0..i] 转变成 s2[0..j] 的最小代价．在我们的题中，也可理解为最小步骤(因为无论啥操作，cost都是１).

这句话当初对我来说并不好理解．为了更容易的让大家理解，举个例子：

本解释将跟随题目要求，cost 均为１.

符号 ＂＊＂ 代表空字符串．

s1 = "a"

s2 = "b"

现在要把 s1 变成 s2，问：最少的步骤是多少？　显然，这种情况下，凭直觉，肯定是1步，既， 1步　substitution.

此时：

这是要对 s1 做 substitution 操作, 将 a 替换成 b:

dp[i, j] = dp[i-1, j-1] + 1 = dp[0, 0] + 1 =  0 + 1 = 1;

若 s1 的第一个字符 a 和 s2 的第一个字符一样的话： dp[1, 1] = dp[0, 0] = 0, 就不需要替换操作了．

* 	a

	^

	i=1

* 	b

	^

	j=1

dp[i = 1, j = 1] 可以写成 dp[i = 0, j = 0] + 1．　就是 s1[0..1] 的串变成 s2[0..1] 的串可表示成 s1的空串变成s2的空串所需次数 + 1.

空串变空串？那还用变？精神病的做法是 ＊ -> a －＞＊,这个cost = 2, 而dp里存的是最小次数或叫做最下距离，那么显然 dp[i = 0, j = 0] = 0 (空串变空串？两个空串有什么好变化的，对吧)

但真的只有这一种办法吗？不是的．看下面：

这是 s1由空变为b 步骤数已知的情况下, 再删除a:

dp[i, j] = dp[i-1][j] + 1 = 1 + 1 = 2

* 	a

^

i-1=0

* 	b

	^

	j=1

还有一个情况：

这是 s1="a" ,删除a变成空的步骤数已知的情况下，再在最后面插入一个b:

dp[i, j] = dp[i][j-1] + 1 = dp[1][0] + 1 = 1 + 1 = 2

* 	a

	^

	i=１

* 	b

^

j-1=0

dp[i, j]只与其左上，左，上，有关．分别为 dp[i-1,j-1], dp[i,j-1] and dp[i-1,j].

总结起来步骤是这样的：

  1. m = s1　的长度，　n = s2　的长度;
  2. 初始化边界：dp[0][j] = j, dp[i][0] = i，其中i = [0,..,m], j = [0,..,n]. 就是空串变某个串, 或某个串变空串的步骤数，肯定是那个串的长度了;
  3. 若 s1[i - 1] = s2[j - 1], 则dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)); 这表示若dp[i - 1][j - 1], dp[i - 1][j]+1, dp[i][j - 1]+1 已知, 则由这３种 case所表达的状态 到 dp[i][i]的状态．我们取上述三种状态的最小值赋值给dp[i][j]. 其中dp[i - 1][j - 1]不用加１是因为s1和s2最后一个字符是一样的，当然不用再加１，否则＋１(就是修改s1最后字符为s2最后字符，其实说最后字符是不妥当的，我们直接认为当前正在处理s1,s2最后面的那个字符，这么想能使问题简单一些.)
  4. 若s1[i - 1] != s2[j - 1], 则dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)); 注意，除了dp[i - 1][j - 1] + 1有变化外，其他没变．
  5. 空间复杂度问题：我们可以维护一个(m+1) * (n+1) 的 dp 矩阵，另一种更好的办法是只维护一个 m 或 n 大小的数组.

人家想法，咱的代码:

方法一:

\(O(m*n)\) time, \(O(m*n)\) extra space.

int minDistance(string word1, string word2) {

	int m = word1.length(), n = word2.length();

	// dp: a (m+1) * (n+1) matrix

	vector < vector<int> > dp(m + 1, vector<int>(n + 1, 0));

	// fill values in boundary

	for (int i = 0; i <= m; i++)

		dp[i][0] = i;

	for (int j = 0; j <= n; j++)

		dp[0][j] = j;

	// dp state transfer formula

	for (int i = 1; i <= m; i++)

		for (int j = 1; j <= n; j++)

			if (word1[i - 1] == word2[j - 1])

				dp[i][j] = min(dp[i - 1][j - 1],

						min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));

			else

				dp[i][j] = min(dp[i - 1][j - 1] + 1,

						min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));

	return dp[m][n];

}

方法二:

\(O(m*n)\) time, \(O(m)\) extra space.

墨迹了挺长时间，没写出来．

看人家的吧．https://leetcode.com/problems/edit-distance/discuss/

写本文的时候发现，文字描述起来好费劲，啰里啰嗦，自己写作水平根本不行啊．

相关文章