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

比眉伴天荒 2023-01-01 14:48 141阅读 0赞

> **微信搜一搜**：`bigsai`  
> **[大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1]**  
> 关注回复**进群**即可加入力扣打卡群，欢迎划水。近期打卡：  
> [LeetCode 92反转链表Ⅱ&93复制ip地址&94二叉树的中序遍历][LeetCode 92_93_ip_94]  
> [LeetCode 96不同的二叉搜索树&95不同的二叉搜索树Ⅱ][LeetCode 96_95]

## 交错字符串 ##

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + ... + sn
    t = t1 + t2 + ... + tm
    |n - m| <= 1
    交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
    提示：a + b 意味着字符串 a 和 b 连接。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]

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

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
    输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
    输出：true

提示：

0 <= s1.length, s2.length <= 100
    0 <= s3.length <= 200
    s1、s2、和 s3 都由小写英文字母组成

**分析**  
这种题一看的话就是一个动态规划类的问题，动态规划类的问题的**难点就是找到状态转移方程**，另一个**重要点就是正确完成初始化**。

先看正常情况的状态转移方程，对于这道题要求的就是问s3能否被s1,s2所连接。如果能够被连接，也就是s3的从前到后任意部分都能由s1和s2拼接而成。我们需要保证的就是从前向后s3的每一个长度都能被成功匹配。

分析s3\[0-i\]是否能够被匹配有下面几种情况：

*  完全由s1匹配，最后一位开始到前面每一位都和s3相等。
 *  完全由s2匹配，最后一位开始到前面每一位都和s3相等。
 *  s1部分和s2部分匹配，但是一定有s1选定长度的最后一位或者s2选定长度的最后一位与s3\[i\]相等(否则无法正确匹配)。并且s1选定长度+s2选定长度=s3选定长度。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]

知道这些关系，我们不妨设一个`dp[s1.length()+1][s2.length()+1]` ,`dp[i+1][j+1]`表示s1的\[0,i\]和s2的\[0,j\]能否匹配s3的\[0,i+j+1\]匹配（这里的0号留给空而不是编号上0的第一位）。所以状态转移方程为：

if(ch1[i]==ch3[i+j+1])//s1串的最后一个和s3匹配
    {
        
     dp[i+1][j+1]=dp[i][j+1];//去掉当前字符前面的结果
    }
    if(!dp[i+1][j+1]&&ch2[j]==ch3[i+j+1])//s2串的最后一个和s3匹配
    {
        
     dp[i+1][j+1]=dp[i+1][j];
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]

当然，具体的实现上，我们需要枚举两个字符串进行求dp，还要进行正确的初始话，因为我们约定这里为null对应的dp为0，比如s1是`abc` s2是 `e` s3是`abce`,那么最终的匹配 `dp[3][0]`表示s1三个，s2零个匹配。而`dp[3][1]`才是表示s1三个，s2一个进行匹配。

而在初始话过程除了`dp[0][0]=true`之外，还需要处理s1不使用和s2不使用的匹配情况(即`dp[0][i]`和`dp[i][0]`).

当然，在具体实现上可以剪枝优化，比如`dp[i][]`一定有其中一个多个为true，否则就不可能成功匹配。

具体的代码为：

public static boolean isInterleave(String s1, String s2, String s3) {
        
    	 if(s1.length()+s2.length()!=s3.length())
    		 return false;
    	 if(s3.equals(""))return true;
    	 char ch1[]=s1.toCharArray();
    	 char ch2[]=s2.toCharArray();
    	 char ch3[]=s3.toCharArray();
    	 
    	 boolean dp[][]=new boolean[s1.length()+1][s2.length()+1];
    	 dp[0][0]=true;//两个空串为true
    	 for(int i=0;i<s1.length();i++)
    	 {
        
    		if(ch1[i]==ch3[i])
    			dp[i+1][0]=true;//注意这里用i+1 
    		else {
        
    			break;
    		}
    	 }
    	 for(int j=0;j<s2.length();j++)
    	 {
        
    		if(ch2[j]==ch3[j])
    			dp[0][j+1]=true;
    		else {
        
    			break;
    		}
    	 }
    	 for(int i=0;i<s1.length();i++)
    	 {
        
    		 char c1=ch1[i];
    		 boolean jud=dp[i+1][0];
    		 for(int j=0;j<s2.length();j++)
    		 {
        
    			 if(c1==ch3[i+j+1])
    			 {
        
    				 dp[i+1][j+1]=dp[i][j+1];
    			 }
    			 if(!dp[i+1][j+1]&&ch2[j]==ch3[i+j+1])
    			 {
        
    				 dp[i+1][j+1]=dp[i+1][j];
    			 }
    			 if(dp[i+1][j+1])
    				 jud=true;
    		 }
    		 if(!jud)
    			 return false;
    	 }
    	 return dp[s1.length()][s2.length()];
    }

原创不易，bigsai请你帮两件事帮忙一下:

1.  star支持一下， 您的肯定是我在平台创作的源源动力。
2.  微信搜索「**bigsai**」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

![image-20201114211553660][]

[Link 1]: https://github.com/javasmall/bigsai-algorithm
[LeetCode 92_93_ip_94]: https://bigsai.blog.csdn.net/article/details/111778579
[LeetCode 96_95]: https://bigsai.blog.csdn.net/article/details/112093545
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]: /images/20221120/9067c53f5daa45ec8315023c9875b74a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]: /images/20221120/d2e795f8e0214d2ebef6e2d518435d1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]: /images/20221120/5529204953414a9fa6f980423d07e99d.png
[image-20201114211553660]: /images/20221120/ab756863185d48979e9a2e12aea0455b.png

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关双序列型动态规划——交错字符串

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

梦里梦外;/ 2022年10月27日 12:07/ 0 赞/ 201 阅读

相关 97. 交错字符串

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

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

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

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

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

相关【动态规划】交错重排

问题两个字符串，不改变原顺序，能否组成目标字符串。 eg： str1:ABC str2:123 aim:A12BC3、123ABC、1A2B3C、………

太过爱你忘了你带给我的痛/ 2022年08月09日 14:58/ 0 赞/ 416 阅读

相关 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 赞/ 161 阅读

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3

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

相关 LeetCode 97 交错字符串

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

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

相关【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 赞/ 171 阅读

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

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

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