Edit Distance

原题链接Edit Distance

讯享网

题目要求，输入两个字符串word1和word2，计算可以将word1转换成word2的最小的操作次数，可以执行的操作如下，每个操作算作1次

• 将word1的某个字符删除
• 在word1当前位置插入一个字符
• 将word1当前位置的字符替换成另一个字符

上面的三个操作每操作一次总操作次数都需要加一，计算最小的操作次数。

这是典型的动态规划问题。

假设word1的长度为m, word2的长度为n，则可以将word1和word2分别表示成

• word1[0, 1, …, m - 1]
• word2[0, 1, …, n - 1]

那么word1[0, 1, ..., i - 1]就表示word1的前i个字符，word2[0, 1, ..., j - 1]就表示word2的前j个字符

定义dp[i][j]表示将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 1]所需要的最小操作次数。

首先明确一点，动态规划是先求子问题的解，再求实际问题的解，对于本题而言。子问题是对于任意的i和j，计算将word1[0, 1, …, i - 1]转换成word2[0, 1, …, j - 1]的最小次数，也就是计算所有dp[i][j]的值

当所有子问题的解都计算完毕后，就可以求解最终的实际问题，这里隐含了一个信息，那就是当要求解最终问题时，所有子问题的解是已知的。

假设现在要将word1[0, 1, ..., i - 1]转换成word2[0, 1, ..., j - 1]，同时假设已经直到了将word1[0, 1, ..., i - 2]转换成word2[0, 1, ..., j - 2]的最小操作此时，即dp[i - 1][j - 1]。
根据上面的叙述，此时的实际问题是计算dp[i][j]，那么所有子问题的解是已知的，即dp[i - 1][j - 1]，dp[i][j - 1]以及dp[i - 1][j]的值是已经知道的（这里只需要使用这三个子问题的解）

那么

• 如果word1[i - 1] == word2[j - 1]，那么对于将字符word1[i - 1]转换到word2[j - 1]是不需要任何操作的
  
  • 将word1[0, 1, ..., i - 2]转换到word2[0, 1, ..., j - 2]，即dp[i][j] = dp[i - 1][j - 1]
• 如果word1[i - 1] != word2[j - 1]，此时有三种方式可以将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 1]
  
  • 将word1[i - 1]替换成word2[j - 1]，此时dp[i][j] = 1 + dp[i - 1][j - 1]
  • 将word1[i - 1]删掉，此时dp[i][j] = 1 + dp[i - 1][j]
  • 在word1的i - 1位置插入字符word2[ j - 1]，此时dp[i][j] = 1 + dp[i][j - 1]

对于替换操作，因为已经直到将word1[0, 1, ..., i - 2]转换到word2[0, 1, ..., j - 2]的最小操作次数即dp[i - 1][j - 1]，那么就可以将word1[i - 1]替换成word2[j - 1]。也就是说，可以先将word1[0 , 1, ..., i - 2]转换到word2[0, 1, ..., j - 2]，然后将word1[i - 1]替换成word2[j - 1]，以达到将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 1]的目的

对于删除操作，因为已经知道将word1[0, 1, ..., i - 2]转换到word2[0, 1, ..., j - 1]的最小操作数即dp[i - 1][j]，那么就可以将word1[i - 1]删掉，也就是说，可以先将word1[0, 1, ..., i - 2]转换到word2[0, 1, ..., j - 1]，然后将word1[i - 1]删掉，以达到将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 1]的目的

对于插入操作，因为已经直到将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 2]的最小操作数即dp[i][j - 1]，那么就可以将word1[0, 1, ..., i - 1]的后面添加字符word2[j - 1]，即word1[0, 1, ..., i - 1] + word2[j - 1] == word2[0, 1, ..., j - 1]。也就是说，可以先将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 2]，然后在word1[0, 1, ..., i - 1]的后面添加字符word2[j - 1]，以达到将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 1]的目的

对于动态规划而言，有递归和迭代两种方法，递归的程序易于理解，但是递归的过程造成的栈开销会影响性能，而迭代恰好相反，不易理解，但是性能高。

递归法是从最终问题递归到一个最小的子问题上，可以理解成从上向下进行，如果使用递归法，那么对于动态规划数组的定义是需要有所改变的。原因是实际问题要求计算将word1转换到word2的最小操作，那么随着递归深度的增加最后到达word1[m - 1]和word2[n - 1]，子问题就变成将word1的某个字符转换成word2的某个字符的最小操作次数。
所以，这里将dp[i][j]的定义改为

• dp[i][j]表示将word1[i, i+1, …, m)转换到word2[j, j+1, …, n)的最小操作次数。

class Solution { public: int minDistance(string word1, string word2) { int n1 = word1.size(); int n2 = word2.size(); vector<vector<int>> dp(n1, vector<int>(n2, INT_MAX)); return minDistance(word1, word2, 0, 0, dp); } private: int minDistance(string& word1, string& word2, int i, int j, vector<vector<int>>& dp) { /* 如果二者都达到末尾，说明转换完毕，返回0即可 */ if(i >= word1.size() && j >= word2.size()) return 0; /* 如果其中一个到达末尾，那么只能通过删除/插入方式使二者相等 */ else if(i >= word1.size() && j < word2.size()) return word2.size() - j; else if(i < word1.size() && j >= word2.size()) return word1.size() - i; if(dp[i][j] != INT_MAX) return dp[i][j]; if(word1[i] == word2[j]) dp[i][j] = std::min(dp[i][j], minDistance(word1, word2, i + 1, j + 1, dp)); /* 将word1[i]替换成word2[j] */ dp[i][j] = std::min(dp[i][j], 1 + minDistance(word1, word2, i + 1, j + 1, dp)); /* 在word1当前位置插入word2[j] */ dp[i][j] = std::min(dp[i][j], 1 + minDistance(word1, word2, i, j + 1, dp)); /* 删除word1[i] */ dp[i][j] = std::min(dp[i][j], 1 + minDistance(word1, word2, i + 1, j, dp)); return dp[i][j]; } };

这种方法效率奇低，原因是每次递归都需要向三个不同的方向递归，即使使用了动态规划数组减少递归次数，但是开销仍然很大。不过这种方法倒是最容易想到的

迭代法就是模拟递归的返回过程，即从最深层的位置向上返回，这就避免后向下递归的过程，也没有所谓的递归栈开销

迭代法的dp定义就和上面相同了，即

• dp[i][j]表示将word1[0, 1, …, i - 1]转换到word2[0, 1, …, j - 1]的最小操作次数

代码如下

讯享网class Solution { public: int minDistance(string word1, string word2) { int n1 = word1.size(); int n2 = word2.size(); vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0)); /* 如果word2为空，那么转换方式就是将word1每个字符删掉，次数就是word1的个数 */ for(int i = 0; i <= n1; ++i) dp[i][0] = i; /* 如果word1为空，那么转换方式就是将依次插入word2对应字符，次数就是word2的个数 */ for(int j = 0; j <= n2; ++j) dp[0][j] = j; for(int i = 1; i <= n1; ++i) { for(int j = 1; j <= n2; ++j) { /* 如果对应字符相等，那么只需要将word1[0, 1, ... i - 2]转换成word2[0, 1, ..., j - 2] */ if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; /* 否则，取三种操作的最小值 */ else dp[i][j] = 1 + std::min(dp[i - 1][j - 1], std::min(dp[i][j - 1], dp[i - 1][j])); } } return dp[n1][n2]; } };

迭代法的效率比较高（至少从代码长度上看也是），不过不太容易理解。
将dp设置为(n1 + 1) * (n2 + 1)的原因是根据dp[i][j]的定义，原因dp[i][j]中的i和j分别表示word1和word2的长度，当其中一个是0时，对相当于对应字符串是空字符

• dp[i][0]表示将word1[0, 1, …, i - 1]转换成空字符，此时操作次数就应该是word1的长度
• dp[0][j]表示将空字符转换成word2[0, 1, …, j - 1]，此时操作次数就应该是word2的长度
• dp[0][0]表示将空字符转换成空字符，此时操作次数就应该是0

当然，凡是动态规划的迭代法都有方法将dp数组降一个维度，这里dp数组是一个二维数组，那么就有办法用一个一维数组解决问题

对比上面的迭代法，每次循环需要的数值有

• dp[i - 1][j - 1]，表示将word1[0, 1, …, i - 2]转换成word2[0, 1, …, j - 2]的最小操作次数
• dp[i][j - 1]，表示将word1[0, 1, …, i - 1]转换成word2[0, 1, …, j - 2]的最小操作次数
• dp[i - 1][j]，表示将word1[0, 1, …, i - 2]转换成word2[0, 1, …, j - 1]的最小操作次数

那么，可不可以只用一维数组就表示上面三个数值呢。
因为是将word1转换成word2，那么假设dp数组的定义为vector<int> dp(word1.size() + 1, 0);

定义dp[i]表示将word1[0, 1, ..., i - 1]转换到word2的最小操作次数，word2的长度是任意的，换句话说，对于任意的j，dp[i]都表示将word1[0, 1, ..., i - 1]转换到word2[0, 1, ..., j - 1]的最小操作次数。

那么，肯定需要从最小的j开始计算，那么可以先将j放在最外层的for循环中，大体的框架如下

class Solution { public: int minDistance(string word1, string word2) { int n1 = word1.size(); int n2 = word2.size(); vector<int> dp(n1 + 1, 0); for(int i = 0; i <= n1; ++i) dp[i] = i; for(int j = 1; j <= n2; ++j) //外层 { for(int i = 1; i <= n1; ++i) //内层 { } } return dp[n1]; } };

想一下，应该如何表示dp[i - 1][j - 1]，dp[i][j - 1]以及dp[i - 1][j]

假设当j = 1时执行一次内层循环，此时dp1, dp2, …., dp[n1]　
当j= 2时再次执行内层循环时，正要计算还没有计算dp[i]时，dp[i]的值是当j = 1时的值
也就是说此时的dp[i]等价于dp[i][j - 1]

假设当j = 1时执行一次内层循环，在内层循环中计算了dp[1], dp[2], ..., dp[i - 1]
正要计算dp[i]时，dp[i - 1]的值等价于dp[i - 1][j]

假设当j = 1时执行了一次内层循环，此时dp1, dp2, …, dp[n1]
当j = 2时再次执行内层循环，在内层循环中计算了dp[1], dp[2], ..., dp[i]，计算dp[i]时记录与dp[i][j - 1]等价的dp[i]，也就是还没有更新dp[i]时的值，记录在遍历prev中。
此时prev表示将word1[0, 1, ..., i - 1]转换成word2[0, 1, ..., j - 2]的值，即dp[i][j - 1]
当计算dp[i + 1]时，prev中的i就变成了i-1，所以表示成dp[i　- 1][j - 1]，说明prev正是与dp[i - 1][j - 1]等价的值
（注，如果dp[i + 1 - 1][j - 1]不容易理解，可以将i + 1看成n，此时要计算将word1[0, 1, ..., n - 1]转换成word2[0, 1, ..., j - 1]的最小操作次数，即dp[n - 1][j - 1]）

以上只是推导了一下二维数组中的dp[i - 1][j - 1]，dp[i][j - 1]和dp[i - 1][j]等价的一维数组对应的值

代码如下

讯享网class Solution { public: int minDistance(string word1, string word2) { int n1 = word1.size(); int n2 = word2.size(); vector<int> dp(n1 + 1, 0); for(int i = 0; i <= n1; ++i) dp[i] = i; for(int j = 1; j <= n2; ++j) { /* dp[0]等价与dp[0][j - 1] */ int prev = dp[0]; dp[0] = j; for(int i = 1; i <= n1; ++i) { /* 此时的dp[i]等价于dp[i][j - 1]，将其赋值给prev * 在下次循环时，prev就代表dp[i - 1][j - 1] * 因为i增加了，此时的i就变为i-1了 */ int temp = dp[i]; if(word1[i - 1] == word2[j - 1]) dp[i] = prev; else /* 此时的dp[i]等价于dp[i][j - 1]，而dp[i - 1]等价于dp[i - 1][j] */ /* prev等价于dp[i - 1][j - 1]，因为prev中的i是此时的i - 1 */ dp[i] = 1 + std::min(prev, std::min(dp[i], dp[i - 1])); prev = temp; } } return dp[n1]; } };