LeetCode 72 Edit Distance

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

Diffculty Hard

Similar Problems [[LeetCode 161] One Edit Distance][] Medium

Analysis

这是算法导论中经典的一道动态规划的题。

显然，这道题的问题空间大小是 M * N，word1 中的每一个字符都可以对应 word2 中的所有字符序列。从 word1 中取任意单个字符 x ，想要转换成 word2 的话，有一下几种情况：

word2 包含两个字符，前一个与 x 相同，那么 x 还需要添加一个字符才能变换到 word2
word2 是空字符串，那么 x 需要删除一个字符才能变换到 word2
word2 只有一个字符，且跟 x 不同，那么 x 需要做一次替换操作才能变换到 word2。

以上是三种需要操作才能有 word1 中单个字符变换到 word2 的情况。

现在，令 dp[i][j] 表示从 word1 的前 i 个字符转换到 word2 的前 j 个字符所需要的步骤，那么 dp[0][0] 则表示空字符串 word1 转换到空字符串 word2 所需的步数，显然是 0，而 dp[0][j] 则表示空字符串转换到 word2 所需的步数，显然，这个是可以确定的，就是 word2 的长度。同样，dp[i][0] 则表示字符串 word1 转换到空字符串 word2 所需的步数，这个显然也可以确定，就是 word1 的长度。因此，动态规划的初始值就可以轻松确定下来：

dp[0][j] = word2.length()
dp[i][0] = word1.length()

接下来，我们需要找到递推式，也就是转换函数。 按照上述的三种操作情况来一一推导

• a) 插入一个字符，也即 word1[0 ... i] == word2[0 ... j - 1]，在字符串 word1[0 ... i] 后面插入 word2[j]，得出： dp[i][j] = dp[i][j - 1] + 1
• b) 删除一个字符，也即 word1[0 ... i - 1] == word2[0 ... j]，把 word1[i] 删除即可，得出 dp[i][j] = dp[i - 1][j] + 1
• c) 替换一个字符，也即 word1[0 ... i - 1] == word2[0 ... j - 1]，两种情况：
  • word1[i] != word2[j]，dp[i][j] == dp[i - 1][j - 1] + 1
  • word1[i] == word2[j]，dp[i][j] == dp[i - 1][j - 1]

由于是求最小编辑距离，因此 dp[i][j] == min(dp[i][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + k)，如果 word1[i] == word2[j]，k = 0, 否则 k = 1 。

计算方向

replace (i - 1, j - 1)      delete (i - 1, j)
insert (i, j - 1)               (i, j)

可见，要求 dp[i][j]，就必须要知道二维矩阵中左上，上方和左下的3个值。所以当我们确定第 0 行和第 0 列的值后，就可以从上到下、从左到右的计算了。]

复杂度 时间 O(NM) 空间 O(NM)

Solutions

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int j = 1; j <= n; j++)
            dp[0][j] = j;

        for(int i = 1; i <= m; i++) {
            dp[i][0] = i;
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j - 1];
                if(word1[i - 1] != word2[j - 1]) dp[i][j]++;
                dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1]+1), dp[i][j]);
            }
        }
        return dp[m][n];
    }
};

Reference

[[LeetCode 161] One Edit Distance]:https://leetcode.com/problems/one-edit-distance