/**
 * @author li_zhe
 * 思路参考leetcode
 * DP,dp[i][j]表示Word1[0~i-1]变为word2[0~j-1]需要的最小步数
 * dp[i][0] = i;
 * dp[0][j] = j;
 * dp[i][j] = dp[i - 1][j - 1], if word1[i - 1] = word2[j - 1];
 * dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1), otherwise.
 */
public class EditDistance {

	public int minDistance(String word1, String word2) {
		if(word1 == null || word2 == null) return 0;
		int len1 = word1.length();
		int len2 = word2.length();
		int[][] dp = new int[len1 + 1][len2 + 1];
		for(int i = 0; i <= len1; i++)
			dp[i][0] = i;
		for(int i = 0; i <= len2; i++)
			dp[0][i] = i;
		for(int i = 1; i <= len1; i++){
			for(int j = 1; j <= len2; j++){
				if(word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
				else dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
			}
		}
		return dp[len1][len2];
	}
	
	public static void main(String[] args) {
		EditDistance distance = new EditDistance();
		System.out.println(distance.minDistance("", ""));
		System.out.println(distance.minDistance("horse", "ros"));
		System.out.println(distance.minDistance("intention", "execution"));
		System.out.println(distance.minDistance("word", "cord"));
	}

}