72. Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character

2. Delete a character

3. Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

這題所求可以從中間過程的子問題來得到，所以用DP來做。dist[i][j]代表把word1[0...i - 1]轉變成word2[0...j - 1]所需要的操作次數。 dp state transition: dp[i][j] = dp[i - 1][j - 1] if word1[i - 1] == word2[j - 1] dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 if word1[i - 1] != word2[j - 1]

// Dynamic Programming
int minDistance(string word1, string word2) { // time: O(m*n); space: O(m*n)
    int m = word1.size(), n = word2.size();
    // dist[i][j] means the number of operations required to convert word1[0...i-1] to word2[0...j-1]
    vector<vector<int> > dist(m + 1, vector<int>(n + 1, 0));
    for (int j = 1; j <= n; ++j)
        dist[0][j] = j;
    for (int i = 1; i <= m; ++i) {
        dist[i][0] = i;
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] != word2[j - 1])
                dist[i][j] = min({dist[i - 1][j], dist[i][j - 1], dist[i - 1][j - 1]}) + 1;
            else
                dist[i][j] = dist[i - 1][j - 1];
        }
    }
    return dist.back().back();
}

但因為dp table中每個grid只跟上方、左邊、左上的grid有關，所以可以用1-D dp array去紀錄搭配其他變數就能完成。

// Space Optimized Dynamic Programming
int minDistance(string word1, string word2) { // time: O(m*n); space: O(n)
    int m = word1.size(), n = word2.size();
    // dist[i][j] means the number of operations required to convert word1[0...i-1] to word2[0...j-1]
    vector<int> dist(n + 1, 0);
    for (int j = 1; j <= n; ++j)
        dist[j] = j;
    for (int i = 1; i <= m; ++i) {
        int upper_left = dist[0];
        dist[0] = i; // initialize the first column
        for (int j = 1; j <= n; ++j) {
            int upper = dist[j];
            if (word1[i - 1] != word2[j - 1])
                dist[j] = min({dist[j], dist[j - 1], upper_left}) + 1;
            else
                dist[j] = upper_left;
            upper_left = upper;
        }
    }
    return dist.back();
}