[LeetCode] 583. 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:

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

两个字符串的删除操作。

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

这道题类似72题。思路是动态规划。这一题是将两个单词 word1 和 word2 中删除任意数量的字符串，使得剩下的部分能一样。既然剩下的部分是一样的（如果剩下的部分不为空），那么说明 word1 和 word2 这两个单词存在相同的 subsequence 子序列。如果能找到这个最长的 subsequence 的长度，那么需要删除的字符个数也就知道了。这里我们需要一个二维数组记录DP值的变化，DP的含义是以 i, j 为结尾的最长公共子序列的长度。转移方程是

如果当前字母是一样的，s.charAt(i - 1) == t.charAt(j - 1)，那么 dp[i][j] = dp[i - 1][j - 1] + 1
如果当前字母不一样，那么dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])

既然DP的定义是两者最长公共子序列的长度，那么需要删除的字母个数 = word1.length() + word2.length() - 2 * 两者最长公共子序列的长度

时间O(mn)

空间O(mn)

Java实现

 1 class Solution {
 2     public int minDistance(String word1, String word2) {
 3         int len1 = word1.length();
 4         int len2 = word2.length();
 5         return len1 + len2 - 2 * helper(word1, word2);
 6     }
 7 
 8     private int helper(String word1, String word2) {
 9         int[][] dp = new int[word1.length() + 1][word2.length() + 1];
10         for (int i = 1; i <= word1.length(); i++) {
11             for (int j = 1; j <= word2.length(); j++) {
12                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
13                     dp[i][j] = dp[i - 1][j - 1] + 1;
14                 } else {
15                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
16                 }
17             }
18         }
19         return dp[word1.length()][word2.length()];
20     }
21 }

[LeetCode] 583. Delete Operation for Two Strings

推荐阅读