72. 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

①字符串(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)。
本问题还有其他方法解，