【Leetcode 热题 100】72. 编辑距离

问题背景

给你两个单词 $wor{d}_1$ 和 $wor{d}_2$， 请返回将 $wor{d}_1$ 转换成 $wor{d}_2$ 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

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

数据约束

• $0\le wor{d}_1.length,wor{d}_2.length\le 500$
• $wor{d}_1$ 和 $wor{d}_2$ 由小写英文字母组成

解题过程

和 昨天的题 实现思路上非常相似，要想清楚的是，如果盯着其中一个字符串来修改，那么所有的操作都可以转化为删除。
在一个字符串上添加，和在另一个字符串上删除，这两种方案在效果和操作次数上是等效的；在一个字符串中替换，和在两个字符串中同时删除，这两种方案，在效果和操作次数上是等价的。

具体实现

递归

class Solution {
    private char[] chW1, chW2;
    private int[][] memo;

    public int minDistance(String word1, String word2) {
        chW1 = word1.toCharArray();
        chW2 = word2.toCharArray();
        int m = chW1.length;
        int n = chW2.length;
        memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(m - 1, n - 1);
    }

    private int dfs(int i, int j) {
        if (i < 0) {
            return j + 1;
        }
        if (j < 0) {
            return i + 1;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        if (chW1[i] == chW2[j]) {
            return memo[i][j] = dfs(i - 1, j - 1);
        }
        return memo[i][j] = Math.min(Math.min(dfs(i - 1, j), dfs(i, j - 1)), dfs(i - 1, j - 1)) + 1;
    }
}

递推

class Solution {
    public int minDistance(String word1, String word2) {
        char[] chW1 = word1.toCharArray();
        char[] chW2 = word2.toCharArray();
        int m = chW1.length;
        int n = chW2.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 0; i < m; i++) {
            dp[i + 1][0] = i + 1;
            for (int j = 0; j < n; j++) {
                dp[i + 1][j + 1] = chW1[i] == chW2[j] ? dp[i][j] : Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
            }
        }
        return dp[m][n];
    }
}