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

?

public class Solution {
    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++) {
        	char c1 = word1.charAt(i-1);
        	for (int j = 1; j <= word2.length(); j++) {
        		char c2 = word2.charAt(j-1);
        		if (c1 == c2) {
        			dp[i][j] = dp[i-1][j-1];
        		} else {
        			int replace = dp[i-1][j-1] + 1;
        			int insert = dp[i][j-1] + 1;
        			int delete = dp[i-1][j] + 1;
        			dp[i][j] = Math.min(Math.min(replace, insert), delete);
        		}
        	}
        }
        return dp[word1.length()][word2.length()];
    }
}

?

Edit Distance

原文：http://hcx2013.iteye.com/blog/2222913