LeetCode 72. 编辑距离

1、题目

image.png

2、分析

这个题目，主要是抽象起来比较难，其实解法还是挺经典的。
1、用自上而下的递归法，主要重叠子的问题
2、用dp数组的自下而上的动态规划解法
动态规划解法其实就是穷举法，把所有的可能都存在dp数组中。
比如字符串1是“rad”，字符串二是“apple”
穷举就是从字符串1的长度为0、1、2、3的时候，变成字符串2需要多少个步骤，
穷举字符串1为“”，然后是“r”，然后是“ra”，然后是“rad”，一步一步推算出来rad需要的步骤。长度+1的时候，就用新增加的字符去判断做什么操作。比如从“r”变成“ra”的时候，就用“a”去判断，如果相同，则步骤增加，要么步骤加一（增加、删除、替换）。

3、代码

递归法：

class Solution {
    int[][] memo = new int[500][500];
    public int minDistance(String word1, String word2) {
        for(int i = 0; i < 500; i++){
            Arrays.fill(memo[i], -1);
        }
        return minDistance(word1, word2, word1.length() - 1, word2.length() - 1);
    }

    private int minDistance(String word1, String word2, int i, int j){
        if(i == -1) return j + 1;
        if(j == -1) return i + 1;
        if(memo[i][j] != -1) return memo[i][j];
        if(word1.charAt(i) == word2.charAt(j)){
            memo[i][j] = minDistance(word1, word2, i - 1, j - 1); //相等
            return memo[i][j];
        }
        memo[i][j] = Math.min(Math.min(minDistance(word1, word2, i - 1, j) + 1, //删除
        minDistance(word1, word2, i - 1, j - 1) + 1), //替换
        minDistance(word1, word2, i, j - 1) + 1); //插入
        return memo[i][j];
    }
}

动态规划

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];
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int i = 0; i <= n; i++){
            dp[0][i] = i;
        }
        for(int i = 1; i <= m; i++){  //注意这两个循环的等号
            for(int j = 1; j <= n; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) //注意这里要-1，因为第一个字符的位置是charAt(0)
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = 1 + Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]),dp[i - 1][j - 1]);
            }
        }
        return dp[m][n];
    }
}