【Leetcode】583.Delete Operation for Two Strings

左手的ㄟ右手 2022-04-14 21:16 109阅读 0赞

### Delete Operation for Two Strings ###

Given two words *word1* and *word2*, find the minimum number of steps required to make *word1* and *word2* the same, where in each step you can delete one character in either string.

**Example 1:**

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

**Note:**

1.  The length of given words won’t exceed 500.
2.  Characters in given words can only be lower-case letters.

#### 解析 ####

题目要求，求出如何能快速的使得`word1`与`word2`两个单词变成一样的。这题是考察最长公共子序列(`LCS`)的应用，求出`LCS`，然后使用

`word1.length+word2.length-2lcs`即可求得结果。

两种解题思路，第一种是比较熟悉的动态规划:

建立状态转移方程，`dp[i][j]`，用来记录`word1`中`【0，i】`与`word2`中索引`[0,j]`中的`LCS`，

*  当`word1[i-1]==word2[j-1]`时，`dp[i][j]=dp[i-1][j-1]`
 *  否则`dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1])`，相当于退而求次，如果`i-1`或`j-1`位置不相等，那么我们使得`word1,word2`向后退一步，用`i`与`j-1`或者`i-1`与`j`来比较。

第二种，使用**记忆化+递归**

创建一个递归函数来求解`LCS`,一个二维数组来存放`[m,n]`位置的`LCS`长度，为了避免重复递归计算，我们可以将之前算得的`LCS`返回。

#### 代码 ####

**记忆化+递归**

public static int minDistance(String word1, String word2) { 
            int mem[][] = new int[word1.length()+1][word2.length()+1];
            return word1.length() + word2.length() - 2 * lcs(word1, word2, word1.length(), word2.length(), mem);
     }
     
    private static int lcs(String s1, String s2, int m, int n, int[][] mem) { 
            if (m == 0 || n == 0) { 
                return 0;
            }
            if (mem[m][n] > 0) { 
                return mem[m][n];
            }
            if (s1.charAt(m - 1) == s2.charAt(n - 1)) { 
                mem[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, mem);
            } else { 
                mem[m][n] = Math.max(lcs(s1, s2, m, n - 1, mem), lcs(s1, s2, m - 1, n, mem));
            }
            return mem[m][n];
        }

**动态规划**

public static int minDistance(String word1, String word2) { 
            int[][] dp = new int[word1.length() + 1][word2.length() + 1];
            for (int i = 0; i <= word1.length(); i++) { 
                for (int j = 0; j <= word2.length(); j++) { 
                    if (i == 0 || j == 0)
                        continue;
                    if (word1.charAt(i - 1) == word2.charAt(j - 1))
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                    else
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
            return word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
        }