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

微信搜一搜：bigsai
大家都在关注的刷题、学习数据结构和算法宝藏项目
关注回复进群即可加入力扣打卡群，欢迎划水。近期打卡：
LeetCode 92反转链表Ⅱ&93复制ip地址&94二叉树的中序遍历
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
2
3
4
5

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

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

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

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

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

知道这些关系，我们不妨设一个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];
}
1
2
3
4
5
6
7
8

当然，具体的实现上，我们需要枚举两个字符串进行求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()];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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

1. star支持一下， 您的肯定是我在平台创作的源源动力。

2. 微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

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