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.

Think

• Two sequence DP
• Setup a 2-D array
• memo[i][j] means the edit distance between word1(1, i) and word2(1, j) on the current position.
• When word1[i] != word2[j], it need increase the distance, so the value of memo[i][j] comes from the minimum of memo[i-1][j], memo[i][j-1] or memo[i-1][j-1] then plus one.
• Initialized value is i or j when word1(0,0) or word2(0,0) (memo[i][0] or memo[0][j])
• The final output is memo[word1.length][word2.length]

Solution

    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    public int minDistance(String A, String B) {
        // write your code here
        if(A == null || B == null)
            return 0;

        int[][] memo = new int[A.length()+1][B.length()+1];
        for(int i = 0; i <= A.length(); i ++) {
            for(int j = 0; j <= B.length(); j ++) {
                if(i == 0 || j == 0)
                    memo[i][j] = (i == 0? (j == 0? 0 : j ): i);
                else
                    memo[i][j] =  (A.charAt(i-1) == B.charAt(j-1) ? memo[i-1][j-1] : Math.min(memo[i-1][j-1], Math.min(memo[i][j-1],memo[i-1][j])) + 1);
            }
        }
        return memo[A.length()][B.length()];
    }