LeetCode 72. Edit Distance

Problem

LeetCode 72. Edit Distance

1. 题目简述

给出两个单词word1和word2，找出从word1变为word2的最少操作数。共计有如下几种操作：

1. Insert a character

2. Delete a character

3. Replace a character

   Input: word1 = “horse”, word2 = “ros”
   Output: 3
   Explanation:
   horse -> rorse (replace ‘h’ with ‘r’)
   rorse -> rose (remove ‘r’)
   rose -> ros (remove ‘e’)

2. 算法思路

参考解法：花花酱LeetCode

也是一道经典老题目了，这种题和正则匹配类的题目基本上是类似的。等下写完本篇Blog再去做一下那道题，也很经典。LeetCode 10. Regular Expression Matching

这种题的做法其实并不复杂，复杂的是分情况讨论。因此实际上是hard难度的题目，真的很难想。

动态规划

我们假设两个字符串为“####a###”和”####b###”，“#”字符是什么我们不用去管，我们只知道我们比较到了一对不一样的字母，‘a’和‘b’，位置为i和j，此时，我们有三种解决方式：插入、删除、替换：

第一种，我们在word1中a的位置后插入一个b，让其和word2中的b相等，然后再去比较剩下的字符串；dp[i][j - 1]
第二种，我们删除word1中的a，然后继续比较word1和word2中剩下的字符；dp[i - 1][j]
第三种，我们将word1中的a替换成b，然后继续比较剩下的字符。dp[i - 1][j - 1]

我们应该取这三种选项中操作次数最少的。
那么我们如何把他用dp递推式的形式展现出来呢？我们假设dp[i][j]为word1的前i个字符转换成word2中前j个字符所需要的最少操作数。

$$dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])$$

base case就是当比较的两个字符串其中一个为空时，另一个需要操作的次数等于它的长度，需要全部删除。

class Solution {
    // top - down解法
    int[][] dp;
    char[] w1, w2;
    public int minDistance(String word1, String word2) {
        int l1 = word1.length(), l2 = word2.length();
        dp = new int[l1 + 1][l2 + 1];
        w1 = word1.toCharArray();
        w2 = word2.toCharArray();
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
        }

        return helper(l1, l2);
    }

    private int helper(int l1, int l2) {
        if (l1 == 0) {
            return l2;
        }
        if (l2 == 0) {
            return l1;
        }
        if (dp[l1][l2] != -1) {
            return dp[l1][l2];
        }

        if (w1[l1 - 1] == w2[l2 - 1]) {
            dp[l1][l2] = helper(l1 - 1, l2 - 1);
        } else {
            dp[l1][l2] = 1 + Math.min(Math.min(helper(l1 - 1, l2), helper(l1, l2 - 1)), helper(l1 - 1, l2 - 1));
        }

        return dp[l1][l2];
    }
}