72. Edit Distance

计算一个词要经过几步操作才能变为另一个词，有3种操作可选：

• 插入一个字符
• 删除一个字符
• 替换一个字符

比如aaa变成bbb就至少要3步，要把每个a都替换成b；如果先把3个a删除，再插入3个b，就需要6步。

如果是以前的我，看到这个题，肯定就直接懵比了。。。

不过好歹也做了这么多题了，还是有些直觉的。这道题一看就是DP，而且相对于以前的10. Regular Expression Matching、44. Wildcard Matching，这道题真是比较简单了。

• 状态定义：dp[i][j]表示word1的前i个字符，变到word2的前j个字符，最少需要几步
• 初始状态：
  • dp[0][0]=0
  • dp[0][j]=j，从一个空字符串变成一个长度为j的字符串，至少需要j步：j次插入
  • dp[i][0]=i，从一个长度为i的字符串变成空字符串，至少需要i步：i次删除
• 状态转移方程：从word1.substring(0,i)变到word2.substring(0,j)有几种方法，取这几种方法中的最小值就可以了：
  • 先从word1.substring(0,i-1)变到word2.substring(0,j-1)，然后做一次替换操作。但这次替换不一定必要，word1.charAt(i)==word2.charAt(j)的情况下就可以省掉一次替换操作。
  • 从word1.substring(0,i-1)变到word2.substring(0,j)，然后删除一个字符
  • 从word1.substring(0,i)变到word2.substring(0,j-1)，然后插入一个字符

根据以上思路，直接写出解法：

public class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null)
            return 0;

        // word1的前i个字符，变到word2的前j个字符，最少需要几步
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        // 初始条件
        dp[0][0] = 0;
        for (int j = 0; j < word2.length(); j++) {
            dp[0][j + 1] = j + 1;
        }
        for (int i = 0; i < word1.length(); i++) {
            dp[i + 1][0] = i + 1;
        }

        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                // 从word1变到word2，有3种变换方法，分别对应插入/删除/替换3种操作，取其中的最小值
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                // 有可能可以省掉一次替换操作
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }
}

只要思路清晰，还是很简单的。