交织的字符串

[编程题]交织的字符串

热度指数：18174 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出三个字符串s1, s2, s3,判断s3是否可以由s1和s2交织而成。

例如：

给定

s1 ="xxyzz",
s2 ="pyyzx",

如果s3 ="xxpyyzyzxz", 返回true

如果s3 ="xxpyyyxzzz", 返回false

示例1

输入

"xxyzz","pyyzx","xxpyyzyzxz"

输出

true

示例2

输入

"xxyzz","pyyzx","xxpyyyxzzz"

输出

false

算法知识视频讲解

华科不平凡

发表于 2020-08-25 15:52:43

"求是否存在"，毫无疑问，又是一道动态规划题。设当前子序列为S1[0..i],S2[0..j],S3[0..i+j+1]，dp[i+1][j+1]==true表示S3[0..i+j]可以由S1[0..i]和S2[0..j]交叉组成，得到如下状态推导公式：如果S1[i]==S3[i+j+1]&am 展开全文

胖胖不吹牛

发表于 2020-03-21 15:48:47

还是想跟大家分享一下我的思路。我觉得这种问题就三个步骤： 1.建dp数组2.添加初始值3.找dp[i]和dp[i-1],dp[i-2]之间的关系多数比较难得dp一般都是dp间关系以及dp的定义不好找。找到后，这种题就会比较好做。代码 import java.util.*; class Soluti 展开全文

FLOYD20191121155229

发表于 2024-09-24 15:21:46

好的，下面是对上述代码的详细介绍，包括每部分的功能和实现逻辑。代码结构类定义：我们定义了一个 Solution 类，其中包含一个成员函数 isInterleave，用于判断字符串是否可以交织。主函数：在 main 函数中，我们实例化 Solution 类并测试了几个示例用例。主要功能函数：isInt 展开全文

ls.joshua

发表于 2020-04-21 17:31:27

这道题比较简单，一开始写的递归，后来改成循环，发现都超时。写了一个简易版本的dp，如下所示：dp[i][j]定义：s1[1...i],s2[1...j]能否顺序匹配 s3[i+j]状态转移方程：有两种状态：1. dp[i][j] = dp[i-1][j], if dp[i-1][j] &&a 展开全文