Edit Distance

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

See here.

Discussion

Two Sequence DP

state: f[i][j]a的前i个字符“配上”b的前j个字符 最少要用几次编辑使得他们相等

跟两个LCS 问题稍有不同，但是思路方向是一致的

Solution

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.length();
        int n = word2. length();
        vector<vector<int> > dist(m+1, vector<int>(n+1, 0));
        for(int i=0; i<=m; i++) {
            dist[i][0] = i;
        }
        for (int j=0; j<=n; j++) {
            dist[0][j] = j;
        }
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(word1[i-1] == word2[j-1]) {//状态转移方程
                    //dist[i][j] = min(dist[i-1][j-1], min(dist[i-1][j],dist[i][j-1]) + 1);
                    dist[i][j] = dist[i-1][j-1];//跟注释掉的上一行效果是一样的
                } else {
                    dist[i][j] = min(dist[i-1][j-1], min(dist[i-1][j],dist[i][j-1]) ) + 1;
                }
            }
        }
        return dist[m][n];
    }
};

Complexity $$O(n^2)$$

// Time:  O(m * n)
// Space: O(min(m, n))

// DP with rolling window
class Solution {
public:
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    int minDistance(string word1, string word2) {
        const size_t m = word1.size();
        const size_t n = word2.size();

        if (m < n) {
            return minDistance(word2, word1);
        }

        vector<vector<int>> steps(2, vector<int>(n + 1, 0));

        for (int j = 0; j < n + 1; ++j) {
            steps[0][j] = j;
        }

        for (int i = 1; i < m + 1; ++i) {
            steps[i % 2][0] = i;
            for (int j = 1; j < n + 1; ++j) {
                steps[i % 2][j] = word1[i - 1] == word2[j - 1] ?
                steps[(i - 1) % 2][j - 1] :
                1 + min(steps[(i - 1) % 2][j - 1],
                        min(steps[(i - 1) % 2][j], steps[i % 2][j - 1]));
            }
        }

        return steps[m % 2][n];
    }
};