给出三个字符串s1, s2, s3,判断s3是否可以由s1和s2交织而成。
例如：
给定
s1 ="xxyzz",
s2 ="pyyzx",
s2 ="pyyzx",
如果s3 ="xxpyyzyzxz", 返回true
如果s3 ="xxpyyyxzzz", 返回false
[编程题]交织的字符串
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length())
return false;
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
//将字符串转换成数组形式
char[] ch1 = s1.toCharArray();
char[] ch2 = s2.toCharArray();
char[] ch3 = s3.toCharArray();
//dp[i][j]表示s3的前i+j个字符能否由s1的前i个字符和s2的前j的字符交叉组成
boolean[][] dp = new boolean[len1+1][len2+1];
dp[0][0] = true;
//只取s1的前i个字符去与s3的前i个字符匹配，得到dp[i][0]的值
for(int i = 1; i <= len1; i++){
dp[i][0] = dp[i-1][0] && (ch1[i-1] == ch3[i-1]);
}
//只取s2的前i个字符去与s3的前j个字符匹配，得到dp[0][j]的值
for(int j = 1; j <= len2; j++){
dp[0][j] = dp[0][j-1] && (ch2[j-1] == ch3[j-1] );
}
//取s1的前i个字符和s2的前j个字符去与s3的前i+j个字符匹配，得到dp[i][j]的值
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; j++){
//dp[i][j]的值为true（s1的前i个字符和s2的前j个字符能交叉组成s3的前i+j个字符）是以下两种情况，满足其一即可：
//(1)dp[i-1][j] && ch1[i-1] == ch3[i+j-1],即s1的前i-1个字符和s2的前j个字符能交叉组成s3的前i+j-1个字符，并且s1的第i个字符等于s3的第i+j字符，说明s1的前i个字符和s2的前j个字符也能交叉组成s3的前i+j个字符
//(2)dp[i][j-1] && ch2[j-1] == ch3[i+j-1],即s1的前i个字符和s2的前j-1个字符能交叉组成s3的前i+j-1个字符，并且s2的第j个字符等于s3的第i+j字符，说明s1的前i个字符和s2的前j个字符也能交叉组成s3的前i+j个字符
dp[i][j] = (dp[i-1][j] && ch1[i-1] == ch3[i+j-1]) || (dp[i][j-1] && ch2[j-1] == ch3[i+j-1]);
}
}
return dp[len1][len2];
}
}
编辑于 2019-07-31 15:10:44
回复(0)
/***
菜鸡的我只能写个递归版
*/
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {if(s1==null||s2==null||s3==null) return false;
if(s1.length()+s2.length()!=s3.length()) return false;
return isInterleave(s1,s1.length()-1,s2,s2.length()-1,s3,s3.length()-1);
}
public boolean isInterleave(String s1, int i, String s2, int j, String s3, int k){
if(i<0&&j<0) return true;
if(i<0){
if(s2.charAt(j) != s3.charAt(k))
return false;
return isInterleave( s1, i, s2, j-1, s3, k-1 );
}
if(j<0){
if(s1.charAt(i) != s3.charAt(k))
return false;
return isInterleave( s1, i-1, s2, j, s3, k-1 );
}
if(s3.charAt(k)!=s1.charAt(i)&&s3.charAt(k)!=s2.charAt(j))
return false;
if(s1.charAt(i)==s2.charAt(j)){
return isInterleave( s1, i, s2, j-1, s3, k-1 )||isInterleave( s1, i-1, s2, j, s3, k-1 );
}else{
if(s1.charAt(i)==s3.charAt(k))
return isInterleave( s1, i-1, s2, j, s3, k-1 );
else
return isInterleave( s1, i, s2, j-1, s3, k-1 );
}
}
}
发表于 2019-07-11 11:46:13
回复(0)
public boolean isInterleave(String s1, String s2, String s3) {
if(s3.length() != s1.length() + s2.length())
return false;
int m=s1.length(),n=s2.length();
boolean[][] dp=new boolean[m+1][n+1];
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i==0&&j==0)dp[i][j]=true;
else if(i==0&&j!=0)dp[i][j]=dp[i][j-1]&&(s2.charAt(j-1)==s3.charAt(i+j-1));
else if(i!=0&&j==0)dp[i][j]=dp[i-1][j]&&(s1.charAt(i-1)==s3.charAt(i+j-1));
else{
dp[i][j]=((dp[i][j]=dp[i][j-1]&&(s2.charAt(j-1)==s3.charAt(i+j-1)))||(dp[i-1][j]&&(s1.charAt(i-1)==s3.charAt(i+j-1))));
}
}
}
return dp[m][n];
}
zhuoshiruozhi
发表于 2018-09-08 16:51:31
回复(0)
//dp[i][j]表示s1的前i个字符和s2的前j个字符可以组成s3的前i+j个字符
//每次用s1或s2中的一个字符去匹配s3中的一个字符，如果能匹配上则dp[i][j] = dp[i-1][j]
//或者dp[i][j] = dp[i][j-1]，如果匹配不上，则dp[i][j]=false
public static boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() == 0 && s2.length() == 0 && s3.length() == 0) return true;
if(s1.length() + s2.length() != s3.length()) return false;
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
for(int i = 0; i <= s1.length(); i++){
for(int j = 0; j <= s2.length(); j++){
if(i >= 1 && s1.charAt(i - 1) == s3.charAt(i + j - 1)){
if(i + j - 1 == 0){
dp[i][j] = true;
}else {
dp[i][j] = dp[i - 1][j];
}
}
if(j >= 1 && s2.charAt(j - 1) == s3.charAt(i + j - 1)){
if(i + j - 1 == 0){
dp[i][j] = true;
}else {
dp[i][j] = dp[i][j - 1] || dp[i][j];
}
}
}
}
return dp[s1.length()][s2.length()];
}
发表于 2017-08-22 14:02:23
回复(0)
递归方法,已AC
解释例如:s1 = abcd,s2 = efgh,s3 = abcdefgh
dp[4,4]表示s1前四个和s2前四个是否可以组合成s3,
就等于dp[3,4]和s1.charat(3)==s3.charat(7)同时true同时true,
或者dp[4,3]和s2.charat(3)==s3.charat(7)同时true;
一步步递归到dp[0][0]则返回true
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length()+s2.length() != s3.length())return false;
boolean[][] dp = new boolean[s1.lengthjavascript:void(0);()+1][s2.length()+1];
return help(s1.length(),s2.length(),s1,s2,s3,dp);
}
boolean help(int m,int n,String s1,String s2,String s3,boolean[][] dp){
if(m == 0 && n == 0)return true;
if(m<0 ||n<0)return false;
return (m>= 1 && s1.charAt(m-1)==s3.charAt(m+n-1) && help(m-1,n,s1,s2,s3,dp))||(n>= 1 && s2.charAt(n-1)==s3.charAt(m+n-1) && help(m,n-1,s1,s2,s3,dp));
}
}
编辑于 2017-08-15 08:57:01
回复(0)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;
if (s1.length() == 0) {
return s2.equals(s3);
}
if (s2.length() == 0) {
return s1.equals(s3);
}
boolean[][] matrix = new boolean[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); ++i) {
for (int j = 0; j <= s2.length(); ++j) {
if (i == 0 && j == 0)
matrix[i][j] = true;
else if (i == 0) {
matrix[i][j] = matrix[i][j - 1] && (s3.charAt(i + j - 1) == s2.charAt(j - 1));
} else if (j == 0) {
matrix[i][j] = matrix[i - 1][j] && (s3.charAt(i + j - 1) == s1.charAt(i - 1));
} else {
matrix[i][j] = (matrix[i][j - 1] && (s3.charAt(i + j - 1) == s2.charAt(j - 1))) || (matrix[i - 1][j] && (s3.charAt(i + j - 1) == s1.charAt(i - 1)));
}
}
}
return matrix[s1.length()][s2.length()];
}
}
发表于 2017-08-10 09:43:24
回复(0)
public boolean isInterleave(String s1, String s2, String s3) { if ((s1.length()+s2.length())!=s3.length()) return false; boolean[][] matrix = new boolean[s2.length()+1][s1.length()+1]; matrix[0][0] = true; for (int i = 1; i < matrix[0].length; i++){ matrix[0][i] = matrix[0][i-1]&&(s1.charAt(i-1)==s3.charAt(i-1)); } for (int i = 1; i < matrix.length; i++){ matrix[i][0] = matrix[i-1][0]&&(s2.charAt(i-1)==s3.charAt(i-1)); } for (int i = 1; i < matrix.length; i++){ for (int j = 1; j < matrix[0].length; j++){ matrix[i][j] = (matrix[i-1][j]&&(s2.charAt(i-1)==s3.charAt(i+j-1))) || (matrix[i][j-1]&&(s1.charAt(j-1)==s3.charAt(i+j-1))); } } return matrix[s2.length()][s1.length()]; }
发表于 2017-03-12 11:14:01
回复(0)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length()) return false;
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
dp[0][0] = true;
for (int i = 1; i < dp.length; i ++ ) {
dp[i][0] = s1.charAt(i - 1) == s3.charAt(i - 1);
}
for (int i = 1; i < dp[0].length; i ++ ) {
dp[0][i] = s2.charAt(i - 1) == s3.charAt(i - 1);
}
for (int i = 1; i < dp.length; i ++ ) {
for (int j = 1; j < dp[0].length; j ++ ) {
if(s3.charAt(i + j - 1) == s1.charAt(i - 1) && dp[i - 1][j]) dp[i][j] = true;
else if(s3.charAt(i + j - 1) == s2.charAt(j - 1) && dp[i][j - 1]) dp[i][j] = true;
}
}
return dp[s1.length()][s2.length()];
}
}
发表于 2016-11-22 18:06:20
回复(0)
问题信息
难度：
9条回答
147收藏
23206浏览
通过挑战的用户
查看代码-
2022-08-26 13:09:56
-
2022-08-20 14:48:58
-
2022-08-11 22:28:30 -
2022-07-20 15:02:39
-
2022-07-11 22:13:11
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
