583. Delete Operation for Two Strings

---

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Example 1:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Example 2:

Input: word1 = "leetcode", word2 = "etco"
Output: 4

Constraints:

• 1 <= word1.length, word2.length <= 500
• word1 and word2 consist of only lowercase English letters.

---

解法1

简单的遍历所有可能的方法, 返回值最小的那个就好了

果不其然的, 这种方法就超时了.

class Solution {
    public int minDistance(String word1, String word2) {
        return helper(word1, 0, word2, 0, 0);
    }
    
    private int helper(String w1, int i, String w2, int j, int count){
        if(i == w1.length())
            return count + (w2.length() - j);
        
        if(j == w2.length())
            return count + (w1.length() - i);
        
        // 分别删去word1 和word2的当前位置的字符, 得到的结果较小的那个就是需要的答案
        int res = 1 + Math.min(helper(w1, i, w2, j + 1, count) , helper(w1, i + 1, w2, j, count));
        
        // 当word1和word2的当前位置字符一致时,可以分别向后移一位继续计算
        if(w1.charAt(i) == w2.charAt(j))
            res = Math.min(res, helper(w1, i + 1, w2, j + 1, count)) ;

        return count + res;
    }
}

---

解法2

既然超时了, 就要想办法减少计算的次数. 可以看到上面计算中有很多重复计算. 那么我们用一个二维数组来保存之前计算的结果.memo[i][j] 表示到 word1[i] 和 word2[j] 为止的最小次数

class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length(), n2 = word2.length();
        // 二维数组的长宽分别比word1和word2的长度多了1
        // 是为了方便计算
        int[][] memo = new int[n1 + 1][n2 + 1];
        
        // 设置word2为空字符串时 到达word1各个位置所需要的step数
        for(int i = 0; i <= n1; i++)
            memo[i][0] = i;
        
        // 设置word1为空字符串时 到达word2各个位置所需要的step数
        for(int j = 0; j <= n2; j++)
            memo[0][j] = j;

        for(int i = 1; i <= n1; i++)
            for(int j = 1; j <= n2; j++){
                // 总是相邻两个位置中较小的那个值加1
                memo[i][j] = Math.min(memo[i - 1][j], memo[i][j - 1]) + 1;
                // 如果字符相等, 可以将左上角的值也加入比较,不过这时不加1
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    memo[i][j] = Math.min(memo[i][j], memo[i - 1][j - 1]);
            }
        
        return memo[n1][n2];
    }

}