LeetCode 97 交错字符串

ゞ浴缸里的玫瑰 2022-03-06 15:12 148阅读 0赞

题目：

给定三个字符串 *s1*, *s2*, *s3*, 验证 *s3* 是否是由 *s1* 和 *s2* 交错组成的。

输入输出：

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
    输出: true

分析：

首先可以分析一下这道题的解空间，比较容易想到的是对于s3中的每个字符我们需要考虑的是用s1或者s2中的字符去代替，这样的话它的解空间应该是o（2^n）的，我们就能想到暴力的解法，再加上一些判断。下面是暴力解法的代码：

class Solution {
    public:
        bool fb(string s1, string s2, string s3, int a, int b, int c){
            if(c == s3.size()){
                return true;
            }
            if(a < s1.size() && b < s2.size() && s1[a] == s3[c] && s2[b] == s3[c]){
                return fb(s1, s2, s3, a + 1, b, c + 1) || fb(s1, s2, s3, a, b + 1, c + 1);
            }
            if(a < s1.size() && s1[a] == s3[c]){
                return fb(s1, s2, s3, a + 1, b, c + 1);
            }
            if(b < s2.size() && s2[b] == s3[c]){
                return fb(s1, s2, s3, a, b + 1, c + 1);
            }
            return false;
        }
        bool isInterleave(string s1, string s2, string s3) {
            if(s1.size() + s2.size() != s3.size()){
                return false;
            }
            return fb(s1, s2, s3, 0, 0, 0);
        }
    };

思路比较简单，对s1,s2,s3都设一个下标为a, b, c。就是对于s3中的每一个字符，如果s1和s2都和该字符一样则返回s1指针后移

和s2后移结果的或，如果其中一个相同，则返回该下标后移的结果，如果都不相同，则直接返回false。这样的话，它的时间复杂度是o（2^n）的，有点高，运行上面的代码内存会超，所以需要寻找其他的方法。

对于这种指数时间复杂的问题，通常都用动态规划的方法来降低时间复杂度，这个题也是一样的。用一个二维数组dp\[i\]\[j\]来表示s1下标为i - 1， s2下标为j - 1 的时候能不能匹配当前的s3。那么状态转移方程为：

dp\[i\]\[j\] = (s1\[i - 1\] == s3\[ i + j - 1\] && dp\[i - 1\]\[j\]) || (s2\[j - 1\] == s3\[i + j - 1\] && dp\[i\]\[j - 1\])

对于位置i，j，可能是通过i匹配得到的，也可能是通过j匹配得到的，所以就有上面的式子，动态规划其实就是通过一个数组来记录之前的状态从而减少搜索的时间。下面是代码：

class Solution {
    public:
        
        bool isInterleave(string s1, string s2, string s3) {
            int len1 = s1.size();
            int len2 = s2.size();
            if(len1 == 0){
                if(s2 == s3) return true;
                else return false;
            }
            if(len2 == 0){
                if(s1 == s3) return true;
                else return false;
            }
            vector<vector<bool>> dp(len1 + 1, vector<bool> (len2 + 1, false));
            dp[0][0] = true;
            if(len1 + len2 != s3.size()){
                return false;
            }
            for(int i = 0; i < len1; ++i)
            dp[i + 1][0] = (s1[i] == s3[i] && dp[i][0]);
          for(int j = 0; j < len2; ++j)
            dp[0][j + 1] = (s2[j] == s3[j] && dp[0][j]);
            for(int i = 1; i < len1 + 1; i++){
                for(int j = 1; j < len2 + 1; j++){
                    dp[i][j] = (s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == 
                                s3[i + j - 1] && dp[i][j - 1]);
                }
            }
            return dp[len1][len2];
        }
    };

动态规划的时间复杂度是o（n^2）的，思路也是比较清晰，这里的思路优点跟最长公共序列相似。

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 97交错字符串(动态规划)

> 微信搜一搜：`bigsai` > [大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1] > 关注回复进群即可加入力扣打卡群，欢迎划水。近期打卡：

比眉伴天荒/ 2023年01月01日 14:48/ 0 赞/ 107 阅读

相关 97. 交错字符串

> 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。 > > 两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会

清疚/ 2022年10月10日 01:56/ 0 赞/ 105 阅读

相关 Leetcode 97. 交错字符串(DP)

题目重述给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串

喜欢ヅ旅行/ 2022年09月08日 03:44/ 0 赞/ 105 阅读

相关 LeetCode97—Interleaving String

LeetCode97—Interleaving String 原题 > Given s1, s2, s3, find whether s3 is formed by

桃扇骨/ 2022年08月21日 02:18/ 0 赞/ 94 阅读

相关 leetcode 97. Interleaving String（字符串交错出现） DFS深度优先遍历 + 很明显很经典的DP动态规划做法

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For examp

桃扇骨/ 2022年06月08日 02:54/ 0 赞/ 115 阅读

相关 [Leetcode][python]Interleaving String/交错字符串

题目大意输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交替而成且不改变s1和s2中各个字符原有的相对顺序。解题思路动态规划

矫情吗；*/ 2022年06月06日 08:35/ 0 赞/ 122 阅读

相关动态规划：交错字符串

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3

我会带着你远行/ 2022年04月10日 13:41/ 0 赞/ 124 阅读

相关 LeetCode 97 交错字符串

题目：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。输入输出：输入: s1 = "aabcc", s2 = "d

ゞ浴缸里的玫瑰/ 2022年03月06日 15:12/ 0 赞/ 149 阅读

相关【Leetcode】97. Interleaving String（动态规划）（字符串组合）

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1

た入场券/ 2022年02月20日 13:41/ 0 赞/ 132 阅读

相关 leetcode：97. 交错字符串（java 回溯）

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例 1: 输入: s1 = "aabcc", s2 = "

r囧r小猫/ 2021年09月28日 09:56/ 0 赞/ 201 阅读