Sunday, April 5, 2015

LeetCode [72] Edit Distance

 72. Edit Distance

Hard

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')
 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//C++: 28ms method1 space O(m*n);
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size();
        int n2 = word2.size();
        vector<vector<int>> dp(n1+1, vector<int>(n2+1));
        for(int j=0; j<=n2; ++j) dp[0][j] = j;
        for(int i=0; i<=n1; ++i) dp[i][0] = i;
        
        for(int i=1; i<=n1; ++i){
            for(int j=1; j<=n2; ++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], min(dp[i-1][j], dp[i][j-1]))+1;
                }
            }
        }
        
        return dp[n1][n2];
    }
};

//C++: 20ms method2 space O(min(m, n));
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        if(n2>n1) return minDistance(word2, word1);
        
        vector<int> row_old(n2+1, 0), row(n2+1, 0);
        for(int j=0; j<=n2; ++j) row_old[j] = j;

        for(int i=1; i<=n1; ++i){
            row[0] = i;
            for(int j=1; j<=n2; ++j){
                if(word1[i-1]==word2[j-1]){
                    row[j] = row_old[j-1];
                }else{
                    row[j] = 1+min(min(row_old[j], row[j-1]), row_old[j-1]);
                }
            }
            row_old = row;
        }

        return row[n2];
    }
};

//Java
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];

        for(int j=1; j<=n; ++j) dp[0][j] = j;
        for(int i=1; i<=m; ++i) dp[i][0] = i;

        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                }
            }
        }

        return dp[m][n];
    }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//Java
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];

        for(int j=1; j<=n; ++j) dp[0][j] = j;
        for(int i=1; i<=m; ++i) dp[i][0] = i;

        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                }
            }
        }

        return dp[m][n];
    }
}
Posted by at
Labels: , , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)