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
解题思路：
DP问题，JAVA实现如下：
public int minDistance(String word1, String word2) {
int[] dp = new int[word2.length() + 1];
for (int i = 0; i < dp.length; i++)
dp[i] = i;
for (int i = 1; i <= word1.length(); i++) {
int upleft = dp[0];
dp[0] = i;
for (int j = 1; j <= word2.length(); j++) {
int temp = dp[j];
if (word1.charAt(i - 1) == word2.charAt(j - 1))
dp[j] = upleft;
else
dp[j] = Math.min(upleft, Math.min(dp[j], dp[j - 1])) + 1;
upleft = temp;
}
}
return dp[word2.length()];
}
Java for LeetCode 072 Edit Distance
原文：http://www.cnblogs.com/tonyluis/p/4509175.html