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

这道题给了我们两个单词,问我们最少需要多少步可以让两个单词相等,每一步我们可以在任意一个单词中删掉一个字符。那么我们分析怎么能让步数最少呢,是不是知道两个单词最长的相同子序列的长度,并乘以2,被两个单词的长度之和减,就是最少步数了。其实这道题就转换成求Longest Common Subsequence最长相同子序列的问题,令博主意外的是,LeetCode中竟然没有这道题,这与包含万物的LeetCode的作风不符啊。不过没事,有这道题也行啊,对于这种玩字符串,并且是求极值的问题,十有八九都是用dp来解的,曾经有网友问博主,如何确定什么时候用greedy,什么时候用dp?其实博主也不不太清楚,感觉dp要更tricky一些,而且出现的概率大,所以博主一般会先考虑dp,如果实在想不出递推公式,那么就想想greedy能做不。如果有大神知道更好的区分方法,请一定留言告知博主啊,多谢!那么决定了用dp来做,就定义一个二维的dp数组,其中dp[i][j]表示word1的前i个字符和word2的前j个字符组成的两个单词的最长公共子序列的长度。下面来看递推式dp[i][j]怎么求,首先来考虑dp[i][j]和dp[i-1][j-1]之间的关系,我们可以发现,如果当前的两个字符相等,那么dp[i][j] = dp[i-1][j-1] + 1,这不难理解吧,因为最长相同子序列又多了一个相同的字符,所以长度加1。由于我们dp数组的大小定义的是(n1+1) x (n2+1),所以我们比较的是word1[i-1]和word2[j-1]。那么我们想如果这两个字符不相等呢,难道我们直接将dp[i-1][j-1]赋值给dp[i][j]吗,当然不是,我们还要错位相比嘛,比如就拿题目中的例子来说,"sea"和"eat",当我们比较第一个字符,发现's'和'e'不相等,下一步就要错位比较啊,比较sea中第一个's'和eat中的'a',sea中的'e'跟eat中的第一个'e'相比,这样我们的dp[i][j]就要取dp[i-1][j]跟dp[i][j-1]中的较大值了,最后我们求出了最大共同子序列的长度,就能直接算出最小步数了,参见代码如下:

解法一:

class Solution {

public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return n1 + n2 - 2 * dp[n1][n2];
    }
};

下面这种方法也是用的dp,但是和上面的dp思路不太一样,这种算法是跟之前那道Edit Distance相同的思路。那道题问我们一个单词通过多少步修改可以得到另一个单词,其实word2删除一个字符,和跟在word1对应的地方加上那个要删除的字符,达到的效果是一样的,并不影响最终的步骤数,所以这道题完全可以按照那道题的解法来做,一点都不需要变动,定义一个二维的dp数组,其中dp[i][j]表示word1的前i个字符和word2的前j个字符组成的两个单词,能使其变相同的最小的步数,讲解可以参看那篇帖子,参见代码入下:

解法二:

class Solution {

public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
        for (int i = 0; i <= n1; ++i) dp[i][0] = i;
        for (int j = 0; j <= n2; ++j) dp[0][j] = j;
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n1][n2];
    }
};

下面这种方法是解法二的递归写法,用的优化的dfs的方法,用memo数组来保存中间计算结果,以避免大量的重复计算,参见代码如下:

解法三:

class Solution {

public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        vector<vector<int>> memo(n1 + 1, vector<int>(n2 + 1, 0));
        return helper(word1, word2, 0, 0, memo);
    }
    int helper(string word1, string word2, int p1, int p2, vector<vector<int>>& memo) {
        if (memo[p1][p2] != 0) return memo[p1][p2];
        int n1 = word1.size(), n2 = word2.size();
        if (p1 == n1 || p2 == n2) return n1 - p1 + n2 - p2;
        if (word1[p1] == word2[p2]) {
            memo[p1][p2] = helper(word1, word2, p1 + 1, p2 + 1, memo);
        } else {
            memo[p1][p2] = 1 + min(helper(word1, word2, p1 + 1, p2, memo), helper(word1, word2, p1, p2 + 1, memo));
        }
        return memo[p1][p2];
    }
};

参考资料:

https://discuss.leetcode.com/topic/89285/java-dp-solution-longest-common-subsequence

https://discuss.leetcode.com/topic/89308/dynamic-programming-and-memoization-solution

https://discuss.leetcode.com/topic/89433/two-pointers-recursive-java-solution-with-memoization

本文转自博客园Grandyang的博客,原文链接:[LeetCode] Delete Operation for Two Strings 两个字符串的删除操作

,如需转载请自行联系原博主。

时间: 2024-10-21 22:16:43

[LeetCode] Delete Operation for Two Strings 两个字符串的删除操作的相关文章

[LeetCode] Minimum ASCII Delete Sum for Two Strings 两个字符串的最小ASCII删除和

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal. Example 1: Input: s1 = "sea", s2 = "eat" Output: 231 Explanation: Deleting "s" from "sea" adds the ASCII value of

ios-比较两个字符串,删除评论元素

问题描述 比较两个字符串,删除评论元素 有两个用逗号分开的NSString,我想要移除第一个字符重复的字符. ex. str1 = 0,1,2,3 str2 = 1,2. output -> str1 = 0,3 and str2 = 1,2. 有一种办法是,用逗号分开两个字符串,但是需要两个NSArray和LOOP循环,然后移除评论元素,但是这样实现起来非常困难,有没有简单办法实现?谢谢好心人帮忙. 解决方案 可以不用循环 但是需要设置好所有的API NSString *str1=@"0

php分割合并两个字符串的函数实例_php技巧

本文实例讲述了php分割合并两个字符串的函数.分享给大家供大家参考.具体实现方法如下: 这里实现把两个字符串进行分割合并,例如str1=aaaa,str2=bbbb,合并后生成abababab /** * Merges two strings in a way that a pattern like ABABAB will be * the result. * * @param string $str1 String A * @param string $str2 String B * @ret

.net-C#删除问题,会把两条数据同时删除

问题描述 C#删除问题,会把两条数据同时删除 我有一张表,编号设为主键,并且是自增长的,然后这张表还有其他字段,工作卡号,姓名,公司系统帐号,密码.现在我有两条数据,工作卡号,姓名,公司系统帐号,密码都一样,就只有编号不同,有人离职,需要删除其中一条数据,为什么我删除的都会是两条同时删除,BLL层的代码是这样: public void delete(string Card_ID) { string strDel = string.Format("insert into DelSystemTabl

经典算法面试题目-判断两个字符串是否是变位词(1.4)

题目 Write a method to decide if two strings are anagrams or not. 写一个函数判断两个字符串是否是变位词. 解答 变位词(anagrams)指的是组成两个单词的字符相同,但位置不同的单词. 比如说, abbcd和abcdb就是一对变位词. 也就是说,2个字符串,不管排列顺序如何,只要全部的单个字符能对应上,就是一对变位词! 该题目有两种做法: 时间复杂度为O(nlogn)的解法 由于组成变位词的字符是一模一样的,所以按照字典序排序后,两

快速比较两个字符串中字符完全相同:即兄弟字符串比较

刚才上网,看到这个问题在好多论坛上得到很大的讨论,于是尝试练习了一下. [问题描述] 对于两个字符串,判定包含的字符是否完全相同.比如:"sabac"和 "basca"算是包含的字符完全相同,并且相同字符的数量也一样要相同,但它们顺序可以不一样. [问题分析] 1.先判断两个字符串的长度是否相同 2. 判断相同长度的字符串中的字符和相同字符的数量是否相同. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Pro

php实现比较两个字符串日期大小的方法

  本文实例讲述了php实现比较两个字符串日期大小的方法.分享给大家供大家参考.具体如下: ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <?php function dateBDate($date1, $date2) { // 日期1是否大于日期2 $month1 = date("m", strtotime($date1)); $month2 = date("m", strtotime($date2

PHP中比较两个字符串找出第一个不同字符位置例子

 这是一个在stackoverflow上的问题. 给出两个长度相等的字符串,找出这两个字符串中第一个不同的字符位置. 一般的做法就会这样:    代码如下: <?php for ($offset = 0; $offset < $length; ++$offset) {     if ($str1[$offset] !== $str2[$offset]) {         return $offset;     } } 而问题下面给出的最佳答案是用异或操作符( ^ ),以前从来没用过这个操作符

jquery判断小数点两位和自动删除小数两位后的数字

 这篇文章主要介绍了jquery判断小数点两位和自动删除小数两位后的数字,需要的朋友可以参考下 jquery判断小数点两位和自动删除小数两位后的数字    基本就是,输入12.235689741    会转换成12.23,不会四舍五入啦    会javascript基础的都应该能看明白啦    不解释   代码如下: $("#fileds").find("input").blur(function(){  var value=$(this).val();  if(v