Edit Distance

/**
Edit Distance:
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:

Insert a character
Delete a character
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')
*/
public class EditDistance {
    public int minDistance(String a, String b) {
        if(a.length() ==0 && b.length()==0)return 0;
        int[][] M = new int[a.length()+1][b.length()+1];
        for(int i =0;i<=b.length();i++){
            M[0][i] = i;
        }
        for(int i =0;i<=a.length();i++){
            M[i][0] = i;
        }
        for(int i =1;i<=a.length();i++){
            for(int j =1;j<=b.length();j++){
                if(a.charAt(i-1) == b.charAt(j-1)){
                    M[i][j] = M[i-1][j-1];
                }else{
                    int temp = Math.min(M[i][j-1]+1,M[i-1][j]+1);
                    M[i][j] = Math.min(temp,M[i-1][j-1]+1);
                }
            }
        }
        return M[a.length()][b.length()];
    }
}