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

Solution:
Think of dynamic programming when met string sequence or matching.
let dist[i][j] donates the main dist between word1[1...i] and word2[1...j]
insert from word1 (left): dist[i][j-1]+1
delete from word1 (upper): dist[i][j-1]+1
replace: dist[i-1][j-1]+1

public class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dist = new int[len1+1][len2+1];
        for(int i=0;i<=len1;i++) dist[i][0]=i;  // initiate, it requires n steps to transfer a n-chars string to "".
        for(int j=0;j<=len2;j++) dist[0][j]=j;
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                dist[i][j] = Math.min(dist[i-1][j]+1, dist[i][j-1]+1);
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dist[i][j] = Math.min(dist[i][j], dist[i-1][j-1]);
                }
                else{
                    dist[i][j] = Math.min(dist[i][j], dist[i-1][j-1]+1);
                }
            }
        }
        return dist[len1][len2];
    }
}