1、前言

题目描述

2、思路

这道题重点是需要了解插入、删除、替换三个操作对于 word1、word2 意味着什么。

假如 word1、word2 都从末尾向头部走，word1 的索引为 i，word2 的索引为 j。

如果 word1[i] == word2[j]，说明此时字符相等，两个索引向前进即可，即 i -1、j - 1。
如果 word1[i] != word2[j]，说明此时字符不想等，那么 word1 变成 word2 有三种操作：删除、插入、替换。

对于删除操作而言，word1 删除此字符，那么 i - 1，但是 word2 不会变，此时 j 还在原位；
对于插入操作而言，word1 肯定是插入与 word2[j] 相等的字符，因为是插入到 i 前面，那么 i 此时不变，j 因为此时字符相等会变成 j - 1；
对于替换操作而言，word1 肯定是替换与 word2 想等的字符，那么此时 i 需要变成 i - 1，且 j 需要变成 j - 1。

basecase 为：如果 word1 减到没了，word2 还有剩余字符，那么 word1 还需要插入 j + 1 个字符（从 0开始）；如果 word2 减到没了，word1 还有剩余字符，那么 word1 需要删除剩余字符，即 i + 1 个字符。

public class NO_72 {

    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();

        return dfs(word1, m - 1, word2, n - 1, new int[m][n]);
    }

    private int dfs(String word1, int m, String word2, int n, int[][] memo){
        if(m < 0){
            return n >= 0 ? n + 1 : 0;
        }

        if(n < 0){
            return m >= 0 ? m + 1 : 0;
        }

        if(memo[m][n] != 0){
            return memo[m][n];
        }

        if(word1.charAt(m) == word2.charAt(n)){
            return dfs(word1, m - 1, word2, n - 1, memo);
        }

        memo[m][n] = min(dfs(word1, m, word2, n - 1, memo) + 1, 
                         dfs(word1, m - 1, word2, n, memo) + 1,
                         dfs(word1, m - 1, word2, n - 1, memo) + 1);

        return memo[m][n];
    }

    private int min(int one, int two, int three){
        return Math.min(one, Math.min(two, three));
    }



    public static void main(String[] args) {
        System.out.println(new NO_72().minDistance("red", "apple"));
    }
}

然后递归是有很多子问题的，所以需要在递归的基础上加备忘录。然后进一步优化的情况下，就是动态规划：
定义数组 dp[i][j] 表示：s1[0 ... i] 和 s2[0 ... j] 的最小编辑距离

3、代码

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // base case
        for(int i = 1; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 1; j <= n; j++){
            dp[0][j] = j;
        }

        // 自底向上求解
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = min(
                        dp[i - 1][j] + 1,
                        dp[i][j - 1] + 1,
                        dp[i - 1][j - 1] + 1
                    );
                }
            }
        }

        // 储存着整个 s1 和 s2 的最小编辑距离
        return dp[m][n];
    }

    private int min(int a, int b, int c){
        return Math.min(a, Math.min(b, c));
    }
}

参考资料

https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/bian-ji-ju-li