力扣解題思路：583. 兩個字串的刪除操作

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

這一題顯然可以使用動態規劃，這裏提供兩種動態規劃的思路。我們用dp[i][j]表示的word1的前i個字元與word2的前j個字元達到相同所需的最小步數，更新規則如下：
（1）如果word1.charAt(i-1) == word2.charAt(j-1)，那麼不需要刪除任何字元，dp[i][j]的值和dp[i - 1][j - 1]的值相同：dp[i][j] = dp[i - 1][j - 1];
（2）如果word1[i - 1] == word2[j - 1]不成立則需要考慮是刪除word1.charAt(i-1)還是 word2.charAt(j-1)，取其中最小的即可，但是無論word1.charAt(i-1) == word2.charAt(j-1)是否成立，都有：
dp[i][j] = Math.min(dp[i][j],Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
然後按照更新規則更新即可：

for(int i=1;i<=word1.length();i++){
    for(int j=1;j<=word2.length();j++){
        if(word1.charAt(i-1) == word2.charAt(j-1)){
            dp[i][j] = dp[i-1][j-1];
        }
        dp[i][j] = Math.min(dp[i][j],Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
    }
}

但是這裏需要注意的是，我們一定要對dp陣列初始化，將最開始的所有值設定爲最大值，如果不初始化則在遍歷陣列是min之後最小值永遠是0，例如dp[i][0]和dp[0][j]也需要賦初始值（相當於一個空串和一個字串比較，當然返回值就是那個字串的長度了，也就是全部刪去即可）：

for(int i=0;i<=word1.length();i++) Arrays.fill(dp[i],Integer.MAX_VALUE);
for(int i=0;i<=word1.length();i++) dp[i][0] = i;
for(int j=0;j<=word2.length();j++) dp[0][j] = j;

完整程式碼如下：

public int minDistance(String word1, String word2) {
    int[][] dp = new int[word1.length()+1][word2.length()+1];
    for(int i=0;i<=word1.length();i++) Arrays.fill(dp[i],Integer.MAX_VALUE);
    for(int i=0;i<=word1.length();i++) dp[i][0] = i;
    for(int j=0;j<=word2.length();j++) dp[0][j] = j;
    for(int i=1;i<=word1.length();i++){
        for(int j=1;j<=word2.length();j++){
            if(word1.charAt(i-1) == word2.charAt(j-1)){
                dp[i][j] = dp[i-1][j-1];
            }
            dp[i][j] = Math.min(dp[i][j],Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
        }
    }
    return dp[word1.length()][word2.length()];
}

當然還有另一個比較巧妙地思路，將該題轉換爲求兩個字串的最長公共子序列問題，那最後結果就是刪去除最長公共子序列的長度即可（之前寫過最長公共子序列的題解，不懂的可以戳這裏ο(=•ω＜=)ρ⌒☆）：

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    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] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return m + n - 2 * dp[m][n];
}

另外，DFS也可以用來解這一題，也是先求最長公共子序列然後返回s1.length() + s2.length() - 2 * lcs(s1, s2, s1.length(), s2.length())即可：

public int minDistance(String s1, String s2) {
    return s1.length() + s2.length() - 2 * lcs(s1, s2, s1.length(), s2.length());//兩個字串的長度之和減去兩倍公共部分即爲需要移除的部分長度之和
}
public int lcs(String s1, String s2, int m, int n) {
    if (m == 0 || n == 0)
        return 0;
    if (s1.charAt(m - 1) == s2.charAt(n - 1))//兩個字串倒數第二個字元相同就意味着可以消除兩個字串最後的字母
        return 1 + lcs(s1, s2, m - 1, n - 1);
    else
        return Math.max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));//若不相同則只消除某個字串的最後一個字元，然後再作比較
}

當然也可以從字串首部開始遍歷：

public int minDistance(String s1, String s2) {
    return s1.length() + s2.length() - 2 * lcs(s1, s2, 0, 0);//兩個字串的長度之和減去兩倍公共部分即爲需要移除的部分長度之和
}
public int lcs(String s1, String s2, int m, int n) {
    if (m == s1.length() || n == s2.length())
        return 0;
    if (s1.charAt(m) == s2.charAt(n))//兩個字串倒數第二個字元相同就意味着可以消除兩個字串最後的字母
        return 1 + lcs(s1, s2, m + 1, n + 1);
    else
        return Math.max(lcs(s1, s2, m, n + 1), lcs(s1, s2, m + 1, n));//若不相同則只消除某個字串的最後一個字元，然後再作比較
}

但是不幸的是，這兩個DFS方法都超時了，接下來對DFS方法進行優化，我們採用記憶化回溯。我們知道在DFS過程中會不斷的回溯，同的 i 和 j 值在不同的函數呼叫路徑中會重複求解，儘管可能在前某次回溯中已經求解過該值了。只要相同的 i 和 j 對應的函數被呼叫一次，我們可以使用 memo 陣列儲存相應函數的返回值來避免後續存取的冗餘。memo[i][j] 被用來儲存函數呼叫 lcs(s1, s2, i, j)的返回值。實際上這就是變相的動態規劃，而memo[i][j]相當於dp陣列：

public int minDistance(String s1, String s2) {
    int[][] memo = new int[s1.length() + 1][s2.length() + 1];//記憶化
    return s1.length() + s2.length() - 2 * lcs(s1, s2, s1.length(), s2.length(), memo);
}
public int lcs(String s1, String s2, int m, int n, int[][] memo) {
    if (m == 0 || n == 0)
        return 0;
    if (memo[m][n] > 0)
        return memo[m][n];
    if (s1.charAt(m - 1) == s2.charAt(n - 1))
        memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
    else
        memo[m][n] = Math.max(lcs(s1, s2, m, n - 1, memo), lcs(s1, s2, m - 1, n, memo));
    return memo[m][n];
}

這樣就不會超出時間限制了，這證明通過返回已經在 memo 陣列中儲存的值，我們可以給搜尋過程極大程度的剪枝。