leetcode Interleaving String

╰+攻爆jí腚メ 2022-08-01 11:08 111阅读 0赞

# 题目 #

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

For example,  
Given:  
s1 = “aabcc”,  
s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true.  
When s3 = “aadbbbaccc”, return false.

题目来源：[https://leetcode.com/problems/interleaving-string/][https_leetcode.com_problems_interleaving-string]

# 分析 #

动态规划。构造二维辅助数组dp\[len1+1\]\[len2+1\]。  
dp\[i+1\]\[j+1\] == true 表示s1\[0…i\]和s2\[0…j\]能够构造成s3\[0…i+j+1\]。  
递推公式：  
dp\[i+1\]\[j+1\] = (dp\[i+1\]\[j\] && (s3.at(i+j+1) == s2.at(j))) || (dp\[i\]\[j+1\] && s3.at(i+j+1) == s1.at(i));

# 代码 #

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

[https_leetcode.com_problems_interleaving-string]: https://leetcode.com/problems/interleaving-string/

发表评论取消回复

表情：

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

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

相关阅读

相关图解LeetCode97：Interleaving String

文章目录理解题意解决方法一：最简单解法解决方法二：动态规划

叁歲伎倆/ 2023年06月15日 11:24/ 0 赞/ 37 阅读

相关 LeetCode-T97-交错字符串（interleaving-string）

题目 [原题链接][Link 1] 题目描述：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。样例 cas

小灰灰/ 2023年02月28日 01:57/ 0 赞/ 16 阅读

相关【NowCoder LeetCode】interleaving-string 动态规划

题目链接：[interleaving-string][] 题意：判断s3是否可以在不改变s1、s2字符顺序的情况下，由s1和s2交织而成。思路：一开始

痛定思痛。/ 2022年11月25日 13:19/ 0 赞/ 112 阅读

相关 leetcode 97. Interleaving String

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

迷南。/ 2022年08月21日 02:25/ 0 赞/ 135 阅读

相关 LeetCode97—Interleaving String

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

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

相关 LeetCode-Interleaving String

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

￡神魔★判官ぃ/ 2022年08月04日 12:58/ 0 赞/ 114 阅读

相关 leetcode Interleaving String

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

╰+攻爆jí腚メ/ 2022年08月01日 11:08/ 0 赞/ 112 阅读

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

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

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

相关 97. Interleaving String

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

àì夳堔傛蜴生んèń/ 2022年05月06日 14:28/ 0 赞/ 139 阅读

相关 leetcode--Interleaving String

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

女爷i/ 2021年10月25日 12:38/ 0 赞/ 139 阅读