Edit Distance

  • tags: [DP_Two_Sequence]

Question

  1. Given two words word1 and word2, find the minimum number of steps required 
  2. to convert word1 to word2. (each operation is counted as 1 step.)
  4. You have the following 3 operations permitted on a word:
  6. Insert a character
  7. Delete a character
  8. Replace a character
  9. Example
  10. Given word1 = "mart" and word2 = "karma", return 3.

题解1 - 双序列动态规划

两个字符串比较，求最值，直接看似乎并不能直接找出解决方案，这时往往需要使用动态规划的思想寻找递推关系。使用双序列动态规划的通用做法，不妨定义f[i][j]为字符串1的前i个字符和字符串2的前j个字符的编辑距离，那么接下来寻找其递推关系。增删操作互为逆操作，即增或者删产生的步数都是一样的。故初始化时容易知道f[0][j] = j, f[i][0] = i, 接下来探讨f[i][j] 和f[i - 1][j - 1]的关系，和 LCS 问题类似，我们分两种情况讨论，即word1[i] == word2[j] 与否，第一种相等的情况有：

  1. i == j, 且有word1[i] == word2[j], 则由f[i - 1][j - 1] -> f[i][j] 不增加任何操作，有f[i][j] = f[i - 1][j - 1].
  2. i != j, 由于字符数不等，肯定需要增/删一个字符，但是增删 word1 还是 word2 是不知道的，故可取其中编辑距离的较小值，即f[i][j] = 1 + min{f[i - 1][j], f[i][j - 1]}.

第二种不等的情况有：

  1. i == j, 有f[i][j] = 1 + f[i - 1][j - 1].
  2. i != j, 由于字符数不等，肯定需要增/删一个字符，但是增删 word1 还是 word2 是不知道的，故可取其中编辑距离的较小值，即f[i][j] = 1 + min{f[i - 1][j], f[i][j - 1]}.

最后返回f[len(word1)][len(word2)]

Python

  1. class Solution: 
  2.     # @param word1 & word2: Two string.
  3.     # @return: The minimum number of steps.
  4.     def minDistance(self, word1, word2):
  5.         len1, len2 = 0, 0
  6.         if word1:
  7.             len1 = len(word1)
  8.         if word2:
  9.             len2 = len(word2)
  10.         if not word1 or not word2:
  11.             return max(len1, len2)
  13.         f = [[i + j for i in xrange(1 + len2)] for j in xrange(1 + len1)]
  15.         for i in xrange(1, 1 + len1):
  16.             for j in xrange(1, 1 + len2):
  17.                 if word1[i - 1] == word2[j - 1]:
  18.                     f[i][j] = min(f[i - 1][j - 1], 1 + f[i - 1][j], 1 + f[i][j - 1])
  19.                 else:
  20.                     f[i][j] = 1 + min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1])
  21.         return f[len1][len2]

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param word1 & word2: Two string.
  5.      * @return: The minimum number of steps.
  6.      */
  7.     int fistance(string word1, string word2) {
  8.         if (word1.empty() || word2.empty()) {
  9.             return max(word1.size(), word2.size());
  10.         }
  12.         int len1 = word1.size();
  13.         int len2 = word2.size();
  14.         vector<vector<int> > f = \
  15.             vector<vector<int> >(1 + len1, vector<int>(1 + len2, 0));
  16.         for (int i = 0; i <= len1; ++i) {
  17.             f[i][0] = i;
  18.         }
  19.         for (int i = 0; i <= len2; ++i) {
  20.             f[0][i] = i;
  21.         }
  23.         for (int i = 1; i <= len1; ++i) {
  24.             for (int j = 1; j <= len2; ++j) {
  25.                 if (word1[i - 1] == word2[j - 1]) {
  26.                     f[i][j] = min(f[i - 1][j - 1], 1 + f[i - 1][j]);
  27.                     f[i][j] = min(f[i][j], 1 + f[i][j - 1]);
  28.                 } else {
  29.                     f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]);
  30.                     f[i][j] = 1 + min(f[i][j], f[i][j - 1]);
  31.                 }
  32.             }
  33.         }
  35.         return f[len1][len2];
  36.     }
  37. };

Java

  1. public class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         int len1 = 0, len2 = 0;
  4.         if (word1 != null && word2 != null) {
  5.             len1 = word1.length();
  6.             len2 = word2.length();
  7.         }
  8.         if (word1 == null || word2 == null) {
  9.             return Math.max(len1, len2);
  10.         }
  12.         int[][] f = new int[1 + len1][1 + len2];
  13.         for (int i = 0; i <= len1; i++) {
  14.             f[i][0] = i;
  15.         }
  16.         for (int i = 0; i <= len2; i++) {
  17.             f[0][i] = i;
  18.         }
  20.         for (int i = 1; i <= len1; i++) {
  21.             for (int j = 1; j <= len2; j++) {
  22.                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  23.                     f[i][j] = Math.min(f[i - 1][j - 1], 1 + f[i - 1][j]);
  24.                     f[i][j] = Math.min(f[i][j], 1 + f[i][j - 1]);
  25.                 } else {
  26.                     f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]);
  27.                     f[i][j] = 1 + Math.min(f[i][j], f[i][j - 1]);
  28.                 }
  29.             }
  30.         }
  32.         return f[len1][len2];
  33.     }
  34. }

源码解析

  1. 边界处理
  2. 初始化二维矩阵(Python 中初始化时 list 中 len2 在前，len1 在后)
  3. i, j 从1开始计数，比较 word1 和 word2 时注意下标
  4. 返回f[len1][len2]

复杂度分析

两重 for 循环，时间复杂度为 O(len1 \cdot len2). 使用二维矩阵，空间复杂度为 O(len1 \cdot len2).