题目描述

感觉和正则表达式匹配这道题很像：同样的两个字符串，同样的二维数组dp，同样的hard。。= =

思路 && 代码 O( $n^2$ )、O( $n^2$ )

使用动态规划的做法，同样多开一行、一列来进行边界处理。
dp[i][j]：以[0, i] 和 [0, j]的子串，word1Son转化成word2Son的最少操作数字
具体做法见注释的 part 和 Case～
主要代码应该是注释 part 2.2 部分的代码，可以这么理解：
0. 对于当前 dp[i][j] 的选取值，i、j匹配的情况显而易见是直接选取dp[i - 1][j - 1]最优
1. 不匹配的情况，有三个最优子结构：左边的dp[i][j - 1]，上边的dp[i - 1][j]，以及左上的dp[i -1][j - 1]。经过思考，我们可以发现这三个最优子结构，可以分别通过增、删、减的方式（操作数 + 1），转移到 dp[i][j] 的状态。
2. 那么显而易见，选取三个子结构的最小值，再增加一个操作数就是当前的最优选择～

class Solution {
    public int minDistance(String word1, String word2) {
        // init
        int m = word1.length();
        int n = word2.length();
        // dp[i][j]:以[0, i] 和 [0, j]的子串，word1Son转化成word2Son的最少操作数字
        int[][] dp = new int[m + 1][n + 1];

        // part 1：边界：
        // part 1.1: 直接插入
        for(int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        // part 1.2: 直接删除
        for(int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }

        // part 2：具体规划过程
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                // part 2.2: 当前字符不匹配：
                if(word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    // Case 1: 删除当前i字符 + dp[i - 1][j]（删）
                    // Case 2: dp[i][j - 1] + 插入j字符（插）
                    // Case 3: dp[i - 1][j - 1] + i 和 j 对着替换一个。（替）
                    // 三种选择，选取步骤最少的一个
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
                // part 2.1: 直接匹配，不用操作
                else {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }   
}