Edit Distance

Edit Distance

Description:

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:

  • Insert a character
  • Delete a character
  • Replace a character
  • Example:*

Given word1 = “mart” and word2 = “karma”, return 3.

分析：

动态规划，下面给出证明。

  1. 最优子结构。

  2. 重叠子问题。

因为只涉及两个word之间的状态转换，所以是个二维dp，关键是如何得到递推关系。

可以假设dp[i][j]是word1的第前i-1个字母和word2的前j-1个字母相互转化所需要的最少步数。分两种情况讨论：

  1. word1[i-1] == word2[j-1]，此时dp[i][j] = dp[i-1][j-1]。(这里有个问题，就是目前本人无法证明dp[i-1][j-1] < dp[i][j-1] + 1且dp[i-1][j-1] < dp[i-1][j] + 1，请高人不吝指教。)

  2. word1[i-1] != word2[j-1]，此时dp[i][j] = min(dp[i-1][j-1] + 1, dp[i][j-1] + 1, dp[i-1][j] + 1)。

有了状态转换式，可以很容易的写出下面的代码。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    int minDistance(string word1, string word2) {
        // write your code here
        int m = word1.size();
        int n = word2.size();
        vector<vector<int> > f(m+1, vector<int>(n+1, 0));
        for (int i = 1; i <= m; i++) {
            f[i][0] = i;
        }
        for (int j = 1; j <= n; j++) {
            f[0][j] = j;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1];
                }
                else {
                    f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
                }
                // f[i][j] = min(f[i-1][j], f[i][j-1]) + 1;
                // f[i][j] = min(f[i][j], word1[i-1] == word2[j-1] ? f[i-1][j-1] : f[i-1][j-1]+1);
            }
        }
        return f[m][n];
    }
};