Edit Distance

Source

• lintcode: 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:

Insert a character
Delete a character
Replace a character

Example
Given word1 = "mart" and word2 = "karma", return 3.

Java

public class Solution {
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length()+1][word2.length()+1];  
        for(int i=0; i <= word1.length(); i++)  
            dp[i][0]=i;  
        for(int j=0; j <= word2.length(); j++)  
            dp[0][j]=j;  

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