Edit Distance

Edit Distance

29%

Accepted

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

Have you met this question in a real interview? 

Yes

Example

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

public class Solution {

    /**

     * @param word1 & word2: Two string.

     * @return: The minimum number of steps.

     */

    public int minDistance(String word1, String word2) {

        // write your code here

        if(word1 == null || word1.length() == 0) return word2.length();

        if(word2 == null || word2.length() == 0) return word1.length();

        int m = word1.length(), n = word2.length();

        int[][] process = new int[m+1][n+1];

        for(int i = 0; i <= m; i++){

            process[i][0] = i;

        }

        

        for(int i = 0; i <= n; i++){

            process[0][i] = i;

        }

        

        for(int i = 1; i <= m; i++){

            for(int j = 1; j <= n; j++){

                if(word1.charAt(i-1) == word2.charAt(j-1)){

                    process[i][j] = process[i-1][j-1];

                } else {

                    process[i][j] = Math.min(process[i][j-1], Math.min(process[i-1][j], process[i-1][j-1])) + 1;

                }

            }

        }

        return process[m][n];

    }

}