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
①字符串(string1+char1,string2+char2)的最小子序列，可以分解为子问题(string1+char1,string2)，(string1,string2+char2)；(string1,string2)的最小编辑距离的解，且此解具有无后效性——最优子结构
②反过来(string1,string2)的解在(string1+char1,string2)，
(string1,string2+char2)，(string1+char1,string2+char2)都要被使用——重叠子问题
符合动态规划条件，假设 F(i,j)是 string1 从 0 到 i 子串和 string2 从 0 到 j 子串的最小编辑距离。转移方程：
F(i+1,j+1) = min { f(i+1,j)+1, f(i,j+1)+1,
f(i1,j1)+(string1[i+1]==string2[j+1]?0:1) }，
需要用一个 m*n 矩阵存放中间结果，时间复杂度是 O(m,n)，空间复杂度是
O(m,n)，但是可以优化.
public class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
if(len1 > len2){
return minDistance(word2, word1);
}
int dp[] = new int[len2+1];
for(int i = 0; i<=len2; i++)
dp[i] = i;
int last, temp;
for(int i = 1; i<=len1; i++){
dp[0] = i;
last = i-1;
for(int j = 1; j<=len2; j++){
temp = dp[j];
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[j] = last;
}else{
dp[j] = 1 + Math.min(last, Math.min(dp[j-1], dp[j]));
}
last = temp;
}
}
return dp[len2];
}
}
这里有两个技巧优化 m*n 的空间复杂度。
①从左往右填 F(i,j)时，依赖上一行的 F(i-1,j),F(i-1,j-1)，以及本行的前一个数F(i,j-1)，F(i,j-1)刚生成，可以直接用，F(i-1,j)在本行尚未被覆盖掉，也可以直接用，只要用一个临时变量保存 F(i-1,j-1)，就可以是空间复杂度降到 O(n)。
②line 5 的转换使得数组长度进一步降到 min(m,n)。
本问题还有其他方法解，
