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都是1).

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

本解释将跟随题目要求,cost 均为1.

符号 "*" 代表空字符串.

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=1 * 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 已知, 则由这3种 case所表达的状态 到 dp[i][i]的状态.我们取上述三种状态的最小值赋值给dp[i][j]. 其中dp[i - 1][j - 1]不用加1是因为s1和s2最后一个字符是一样的,当然不用再加1,否则+1(就是修改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/

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