EditDistance [source code]

public class EditDistance {
static
/******************************************************************************/
class Solution {
    public int minDistance(String word1, String word2) {
        char[] chs1 = word1.toCharArray (), chs2 = word2.toCharArray ();
        int[][] dp = new int[chs1.length + 1][chs2.length + 1];
        for (int i = 0; i < dp.length; i++) for (int j = 0; j < dp[0].length; j++) {
            if (i == 0 && j == 0)
                dp[i][j] = 0;
            else if (i == 0)
                dp[i][j] = dp[i][j - 1] + 1;
            else if (j == 0)
                dp[i][j] = dp[i - 1][j] + 1;
            else if (chs1[i - 1] == chs2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min (dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }

    int min (int... nums) {
        int min = Integer.MAX_VALUE;
        for (int num : nums) if (num < min)
            min = num;
        return min;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        EditDistance.Solution tester = new EditDistance.Solution();
    }
}

老题了, 拿来骗一下数量;

这么熟悉的题目居然也做了好久, 丢人; 最后速度是18ms (11%);

没有editorial;

@jianchao.li.fighter said in 20ms Detailed Explained C++ Solutions (O(n) Space):

This is a classic problem of Dynamic Programming. We define the state dp[i][j] to be the minimum number of operations to convert word1[0..i - 1] to word2[0..j - 1]. The state equations have two cases: the boundary case and the general case. Note that in the above notations, both i and j take values starting from 1.

For the boundary case, that is, to convert a string to an empty string, it is easy to see that the mininum number of operations to convert word1[0..i - 1] to "" requires at least i operations (deletions). In fact, the boundary case is simply:

  1. dp[i][0] = i;
  2. dp[0][j] = j.

Now let's move on to the general case, that is, convert a non-empty word1[0..i - 1] to another non-empty word2[0..j - 1]. Well, let's try to break this problem down into smaller problems (sub-problems). Suppose we have already known how to convert word1[0..i - 2] to word2[0..j - 2], which is dp[i - 1][j - 1]. Now let's consider word[i - 1] and word2[j - 1]. If they are euqal, then no more operation is needed and dp[i][j] = dp[i - 1][j - 1]. Well, what if they are not equal?

If they are not equal, we need to consider three cases:

  1. Replace word1[i - 1] by word2[j - 1] (dp[i][j] = dp[i - 1][j - 1] + 1 (for replacement));
  2. Delete word1[i - 1] and word1[0..i - 2] = word2[0..j - 1] (dp[i][j] = dp[i - 1][j] + 1 (for deletion));
  3. Insert word2[j - 1] to word1[0..i - 1] and word1[0..i - 1] + word2[j - 1] = word2[0..j - 1] (dp[i][j] = dp[i][j - 1] + 1 (for insertion)).

Make sure you understand the subtle differences between the equations for deletion and insertion. For deletion, we are actually converting word1[0..i - 2] to word2[0..j - 1], which costs dp[i - 1][j], and then deleting the word1[i - 1], which costs 1. The case is similar for insertion.

Putting these together, we now have:

  1. dp[i][0] = i;
  2. dp[0][j] = j;
  3. dp[i][j] = dp[i - 1][j - 1], if word1[i - 1] = word2[j - 1];
  4. dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1), otherwise.

The above state equations can be turned into the following code directly. 

class Solution {   
public:  
    int minDistance(string word1, string word2) {   
        int m = word1.length(), n = word2.length();  
        vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));  
        for (int i = 1; i <= m; i++)  
            dp[i][0] = i;  
        for (int j = 1; j <= n; j++)  
            dp[0][j] = j;    
        for (int i = 1; i <= m; i++) {  
            for (int j = 1; j <= n; j++) {  
                if (word1[i - 1] == word2[j - 1])   
                    dp[i][j] = dp[i - 1][j - 1];  
                else dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));  
            }  
        }  
        return dp[m][n];  
    }  
};

Well, you may have noticed that each time when we update dp[i][j], we only need dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]. In fact, we need not maintain the full m*n matrix. Instead, maintaing one column is enough. The code can be optimized to O(m) or O(n) space, depending on whether you maintain a row or a column of the original matrix.

The optimized code is as follows. 

class Solution {   
public:  
    int minDistance(string word1, string word2) {  
        int m = word1.length(), n = word2.length();  
        vector<int> cur(m + 1, 0);  
        for (int i = 1; i <= m; i++)  
            cur[i] = i;  
        for (int j = 1; j <= n; j++) {  
            int pre = cur[0];  
            cur[0] = j;  
            for (int i = 1; i <= m; i++) {  
                int temp = cur[i];  
                if (word1[i - 1] == word2[j - 1])  
                    cur[i] = pre;  
                else cur[i] = min(pre + 1, min(cur[i] + 1, cur[i - 1] + 1));  
                pre = temp;  
            }  
        }  
        return cur[m];   
    }  
};

Well, if you find the above code hard to understand, you may first try to write a two-column version that explicitly maintains two columns (the previous column and the current column) and then simplify the two-column version into the one-column version like the above code :-)

如果是要做到O(N)的space, 只需要维护一个row, 不要以为是两个! 自己想想为什么;

ED作为一个非常经典的老题, 真正面试如果碰到, 问问你空间优化应该是再正常不过的了;

好像并没有必要自己定义min:

@King_YL said in Java DP solution - O(nm):

quick question, why use the complex form like "a < b ? (a < c ? a : c) : (b < c ? b : c)"? I think using "Math.min(a,Math.min(b,c))" is much easier to observe

比较熟悉的老题目了, discussion基本就是这个解法了, like there was any other;

submission最优解: 7(99): 

class Solution {  
    public int minDistance(String s1, String s2) {  
        int[][] mem = new int[s1.length()+1][s2.length()+1];  
        return auxEditDistance2(s1.length(), s2.length(), s1, s2, mem);  
    }  

    private int auxEditDistance2(int i, int j, String s1, String s2, int[][] mem) {  
        if (i == 0)  
            return j;  
        if (j == 0)  
            return i;  

        if(mem[i][j]!=0)  
            return mem[i][j];  

        if (s1.charAt(i - 1) == s2.charAt(j - 1))  
            return mem[i][j] = auxEditDistance2(i - 1, j - 1, s1, s2, mem);  
        else {  
            int insertCost = auxEditDistance2(i, j - 1, s1, s2, mem);  
            int replaceCost = auxEditDistance2(i - 1, j - 1, s1, s2, mem);  
            int deleteCost = auxEditDistance2(i - 1, j, s1, s2, mem);  
            return mem[i][j] = Math.min(insertCost, Math.min(replaceCost, deleteCost)) + 1;  
        }  
    }  
}

利用了recursion的优势;

另外, 这题好像用charAt并没有比toCharArray有太多劣势;

Problem 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

Difficulty:Hard
Total Accepted:108.7K
Total Submissions:335.5K
Contributor:LeetCode
Related Topics
stringdynamic programming
Similar Questions
One Edit DistanceDelete Operation for Two StringsMinimum ASCII Delete Sum for Two Strings

results matching ""

    No results matching ""