Tuesday, October 16, 2012

[LeetCode] Edit Distance


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:
a) Insert a character
b) Delete a character
c) Replace a character
解题思路: 典型的DP
        1. S(i)->T(j) = S(i-1)->T(j-1) if s(i) == t(j)
        2. if s(i) != t(j), 有三个选择,2.1 插入 S(i)->T(j-1) = S(i) ->T(j) 2.2 删除,S(i-1, j) ->S(i, j)   2.3. 替换 S(i-1)->T(j-1) = S(i) -> T(j)





public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        
        int[][] minDis = new int[len1+1][len2+1];
        
        for(int i = 0; i <= len1; i++){
            for(int j = 0; j <= len2; j++){
                if(i == 0){
                    minDis[i][j] = j;
                }else if( j == 0){
                    minDis[i][j] = i;
                }else{
                    if(word1.charAt(i-1) == word2.charAt(j-1)){
                        minDis[i][j] = minDis[i-1][j-1]; 
                    }else{
                        int min = Math.min(minDis[i-1][j-1], minDis[i][j-1]);
                        min = Math.min(min, minDis[i-1][j]);
                        
                        minDis[i][j] = min + 1;
                    }
                }
            }
        }
        
        return minDis[len1][len2];
    }

No comments:

Post a Comment