对于三个字符串A，B，C。我们称C由A和B交错组成当且仅当C包含且仅包含A，B中所有字符，且对应的顺序不改变。请编写一个高效算法，判断C串是否由A和B交错组成。
给定三个字符串A,B和C，及他们的长度。请返回一个bool值，代表C是否由A和B交错组成。保证三个串的长度均小于等于100。
测试样例：
"ABC",3,"12C",3,"A12BCC",6
返回：true
[编程题]字符串交错组成
动态规划：dp[i][j]表示aim[0...i+j-1]能否用str1[0...i-1]和str2[0...j-1]组成
public boolean chkMixture(String str1, int n, String str2, int m, String aim, int v) {
if (str1 == null || str2 == null || aim == null)
return false;
char[] ch1 = str1.toCharArray();
char[] ch2 = str2.toCharArray();
char[] chaim = aim.toCharArray();
if (m + n != v)
return false;
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
if (dp[i - 1][0] && ch1[i - 1] == chaim[i - 1])
dp[i][0] = true;
}
for (int j = 1; j <= m; j++) {
if (dp[0][j-1] && ch2[j - 1] == chaim[j - 1])
dp[0][j] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if ((dp[i - 1][j] && ch1[i - 1] == chaim[i + j - 1])
|| (dp[i][j - 1] && ch2[j - 1] == chaim[i + j - 1]))
dp[i][j] = true;
}
}
return dp[n][m];
}
发表于 2017-12-24 21:15:47
回复(1)
更多回答
import java.util.*;
public class Mixture {
public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
if(n + m != v) return false;
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i ++) {
if(A.charAt(i - 1) == C.charAt(i - 1)) dp[i][0] = true;
else break;
}
for (int j = 1; j <= m; j ++) {
if(B.charAt(j - 1) == C.charAt(j - 1)) dp[0][j] = true;
else break;
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
dp[i][j] = (A.charAt(i - 1) == C.charAt(i + j - 1) && dp[i - 1][j]) || (B.charAt(j - 1) == C.charAt(i + j - 1) && dp[i][j - 1]);
}
}
return dp[n][m];
}
}
编辑于 2017-03-16 22:24:40
回复(2)
用DP做并不复杂
import java.util.*;
public class Mixture {
public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
// write code here
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= m; ++j) {
if(dp[i][j]) {
if(i < n && A.charAt(i) == C.charAt(i + j)) {
dp[i + 1][j] = true;
}
if(j < m && B.charAt(j) == C.charAt(i + j)) {
dp[i][j + 1] = true;
}
}
}
}
return dp[n][m];
}
}
发表于 2017-05-10 01:17:14
回复(5)
import java.util.*;
public class Mixture {
public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
// write code here
char[] a = A.toCharArray();
char[] b = B.toCharArray();
char[] c = C.toCharArray();
boolean[][] dp = new boolean[a.length + 1][b.length + 1];
dp[0][0] = true;
for (int i = 1; i <= a.length; ++i) {
if (a[i - 1] == c[i - 1]) {
dp[i][0] = true;
} else {
break;
}
}
for (int j = 1; j <= b.length; ++j) {
if (b[j - 1] == c[j - 1]) {
dp[0][j] = true;
} else {
break;
}
}
for (int i = 1; i <= a.length; ++i) {
for (int j = 1; j <= b.length; ++j) {
if (dp[i - 1][j] && c[i + j - 1] == a[i - 1]) {
dp[i][j] = true;
continue;
}
if (dp[i][j - 1] && c[i + j - 1] == b[j - 1]) {
dp[i][j] = true;
}
}
}
return dp[a.length][b.length];
}
}
发表于 2016-09-10 14:00:42
回复(0)
//递归求解
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C, int v) {
if(n+m!=v)
return false;
if((m==0&&A==C)||(n==0&&B==C))
return true;
if((m==0&&A!=C)||(n==0&&B!=C))
return false;
if(A[0]==C[0]&&B[0]!=C[0])
return chkMixture(A.substr(1),n-1,B,m,C.substr(1),v-1);
else if(A[0]!=C[0]&&B[0]==C[0])
return chkMixture(A,n,B.substr(1),m-1,C.substr(1),v-1);
else if(A[0]==C[0]&&B[0]==C[0])
return chkMixture(A.substr(1),n-1,B,m,C.substr(1),v-1)||chkMixture(A,n,B.substr(1),m-1,C.substr(1),v-1);
else
return false;
}
};
发表于 2016-08-15 10:26:30
回复(3)
classMixture {
public:
bool chkMixture(string A, intn, string B, intm, string C, intv) {
// write code here
if(n+m!=v)returnfalse;
if(v == 0)returntrue;
if(A[0] == C[0] && B[0] != C[0]){
returnchkMixture(&A[1],n-1,B,m,&C[1],v-1);
}
if(A[0] != C[0] && B[0] == C[0]){
returnchkMixture(A,n,&B[1],m-1,&C[1],v-1);
}
if(A[0] == C[0] && B[0] == C[0]){
returnchkMixture(&A[1],n-1,B,m,&C[1],v-1)||chkMixture(A,n,&B[1],m-1,&C[1],v-1);
}
returnfalse;
}
}
看了下别人的代码，感觉最简短精炼的还属递归，简化代码，增强可读性，欢迎参考
发表于 2015-08-06 18:22:16
回复(3)
分析
动态规划就是从中间截断，然后从后往前看，从前往后算。
- 定义状态；
- 再向前找出此状态所依赖的状态；
<- <-
A|BC 12|C
^ <--- ^
i A12|BCC j
^
i+j-1 定义状态：
C字符串的前
i+j-1个字符可由A字符串的前i个字符和B字符串的前j个字符交错组成。f[i][j]表示C字符串的前i+j-1个字符能否由A字符串的前i个字符和B字符串的前j个字符交错组成，值为true或false。再向前找出此状态所依赖的状态：
f[i][j]可以由f[i-1][j]和cc[i+j-1]==aa[i-1]组成，也可以由f[i][j-1]和cc[i+j-1]==bb[i-1]组成f[i][j]=(f[i-1][j]&&cc[i+j-1]==aa[i-1])||(f[i][j-1]&&cc[i+j-1]==bb[i-1])初始化
f[0][0]表示A，B两个为空串时，所能组成的C也为空串，值为true。f[0][j]和f[i][0]表示A或B其中之一为空串时，C串仅由其中一个串组成，只需考虑依赖状态的对应一种即可。
public static boolean chkMixture(String A, int n, String B, int m, String C, int v) {
if(n+m!=v) return false;
char[] aa = A.toCharArray();
char[] bb = B.toCharArray();
char[] cc = C.toCharArray();
boolean[][] f= new boolean[n+1][m+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0&&j==0) f[i][j]=true;
else if(i==0&&j!=0){
f[i][j]=(f[i][j-1] && bb[j-1]==cc[i+j-1]);
}else if(i!=0&&j==0){
f[i][j]=(f[i-1][j] && aa[i-1]==cc[i+j-1]);
}else{
f[i][j]=((f[i][j-1] && bb[j-1]==cc[i+j-1])||(f[i-1][j] && aa[i-1]==cc[i+j-1]));
}
}
}
return f[n][m];
}
发表于 2020-04-29 15:45:13
回复(0)
python 递归解法
# -*- coding:utf-8 -*- class Mixture: def chkMixture(self, A, n, B, m, C, v): if self.check(A, B, C): return True return False def check(self, A, B, C): if A == C or B == C: return True if A[0] == C[0] and self.check(A[1:], B, C[1:]): return True if B[0] == C[0] and self.check(A, B[1:], C[1:]): return True return False
发表于 2019-08-10 22:36:21
回复(0)
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C, int v) {
bool dp[n+1][m+1];
memset(dp,false,sizeof(dp));
dp[0][0] = true;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(dp[i][j]) { if(i<n && A[i]==C[i+j]) dp[i+1][j] = true; if(j<m && B[j]==C[i+j]) dp[i][j+1] = true; } return dp[n][m];
}
};
发表于 2017-10-22 01:12:10
回复(0)
#递归版本
if n == 0 or m == 0 or v == 0:
return True
if A[0] == C[0] and B[0] != C[0]:
return self.chkMixture(A[1:], n-1, B, m, C[1:], v-1)
if B[0] == C[0] and A[0] != C[0]:
return self.chkMixture(A, n, B[1:], m-1, C[1:], v-1)
if A[0] == C[0] == B[0]:
return self.chkMixture(A[1:], n-1, B, m, C[1:], v-1) or self.chkMixture(A, n, B[1:], m-1, C[1:], v-1)
return False
#动态规划版本 class Mixture:
def chkMixture(self, A, n, B, m, C, v):
# write code here
dp = [[False for i in range(m+1)] for j in range(n+1)]
for i in range(n+1):
for j in range(m+1):
if i == j == 0:
dp[i][j] = True
elif i == 0 and j != 0:
dp[i][j] = dp[i][j-1] and B[j-1] == C[j-1]
elif i != 0 and j == 0:
dp[i][j] = dp[i-1][j] and A[i-1] == C[i-1]
elif A[i-1] == C[i+j-1] and dp[i-1][j] == True:
dp[i][j] = True
elif B[j-1] == C[i+j-1] and dp[i][j-1] == True:
dp[i][j] = True
return dp[-1][-1]
编辑于 2017-08-09 16:27:25
回复(0)
package alex.suda.dp;
import java.util.Scanner;
public class test5 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
String A = scanner.next();
int m = scanner.nextInt();
String B = scanner.next();
int v = scanner.nextInt();
String C = scanner.next();
System.out.print(chkMixture(A, n, B, m, C, v));
}
}
public static boolean chkMixture(String A, int n, String B, int m, String C, int v) {
// d[i][j]表示当A在i位处是交错的同时s2在j位处是交错的s3在i+j处是否是交错的。
// 如果A和B在当前位置是空，C也是空，为true
// 如果A为空，B之前的位置是交错的而且s2在当前位置和s3的当前位置字符是一样的，则视为true；反之s2为空时情况是一样的。
// A和B都不为空，从i-1,j到达i,j处时，如果i-1,j处是交错的而i处与当前的s3一致，则视为true;
// 当我们从i,j-1到达i,j处时，如果i,j-1处是交错的而j处与当前的s3一致，则视为true;
boolean[][] d = new boolean[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 && j == 0) {
d[i][j] = true;
} else if (i == 0) {
d[i][j] = (d[i][j - 1] && B.charAt(j - 1) == C.charAt(i + j - 1));
} else if (j == 0) {
d[i][j] = (d[i - 1][j] && A.charAt(i - 1) == C.charAt(i + j - 1));
} else {
d[i][j] = (d[i - 1][j] && A.charAt(i - 1) == C.charAt(i + j - 1))
|| (d[i][j - 1] && B.charAt(j - 1) == C.charAt(i + j - 1));
}
}
}
return d[n][m];
}
}
发表于 2016-10-06 22:26:49
回复(0)
bool chkMixture(string A, int n, string B, int m, string C, int v) {
// write code here
if((n+m) != v)
return false;
if(!v)
return true;
if(n==v && A==C)
return true;
else if(n==v)
return false;
if(m==v && B==C)
return true;
else if(m==v)
return false;
vector<vector<bool> > c(n+1, vector<bool>(m+1, false));
c[0][0] = true;
for(int i = 1; i <= n; ++i)
if(A[i-1] == C[i-1])
c[i][0] = c[i-1][0];
for(int i = 1; i <=m; ++i)
if(B[i-1] == C[i-1])
c[0][i] = c[0][i-1];
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(!c[i][j] && A[i-1] == C[i+j-1])
c[i][j] = c[i-1][j];
if(!c[i][j] && B[j-1] == C[i+j-1])
c[i][j] = c[i][j-1];
}
}
return c[n][m];
}
发表于 2016-03-08 08:48:32
回复(1)
真的，原来写程序递归真的很容易写出来
但是把他转换成dp就不知道怎么做了，看了左神的视频之后真的是有一点启发了，比如这道题，递归是真的很好想的，但是如何把递归转换成时间复杂度更小的dp呢，首先看递归需要多少个参数，其中参数变化的部分都是dp用到的矩阵维度。
这个题我们变化的其实就是三个字符串的指针，就是当前字符串遍历到的那个位置。
"ABC","12C","A12BCC"就比如这题的示例，我们假如比较到了BCC中的B，我们判断这个时候true或者false的时候，我们需要知道的是前面A12的比较情况，我们就可以把dp[][]中前一次的情况取出来再加上这一次的比较结果在写入新的dp当中，知道我们目标字符串遍历完毕即可。
class Mixture {public:bool chkMixture(string A, int n, string B, int m, string C, int v) {// write code hereif(n+m!=v)return false;vector<vector<bool>> dp (n+1,vector<bool>(m+1,false));int a=0;int b=0;dp[0][0] = true;for(int i=0;i<v;i++){if(A[a] == C[i] && dp[a][b] == true){a++;dp[a][b] = true;}if(B[b] == C[i] && dp[a][b] == true){b++;dp[a][b] = true;}}return dp[n][m];}};
发表于 2016-08-03 21:59:52
回复(3)
#这题测试用例应该不完备
#下面算法的思想就是：先比较A是否包含在C中，再比较B是否包含在C中，完全没使用到动态规划
class Mixture:
def chkMixture(self, A, n, B, m, C, v):
# write code here
flag_A = True
flag_B = True
i = 0
j = 0
#先比较A是否包含在C中
while i < n and j < v:
if A[i] == C[j]:
i += 1
j += 1
#当j已遍历玩C，但是A数组中还有字符未在C中找到时，返回FALSE
if i < n and j >= v:
flag_A = False
break
i = 0
j = 0
#再比较B是否包含在C中
while i < m and j < v:
if B[i] == C[j]:
i += 1
j += 1
if i < m and j >= v:
flag_B = False
break
return (flag_A and flag_B)
发表于 2017-08-22 21:15:03
回复(0)
python递归解法，通过了所有测试，不过还是不如DP解法。。先放上去，大家可以参考一下：
class Mixture:
def chkMixture(self, A, n, B, m, C, v):
# write code here
if not n+m==v:
return False
self.canForm=False
self.dfs(A,B,C)
return self.canForm
def dfs(self, s1, s2, s3):
if self.canForm:
return
if s3 == "":
self.canForm = True
return
if s1 and s1[0] == s3[0]:
self.dfs(s1[1:], s2, s3[1:])
if s2 and s2[0] == s3[0]:
self.dfs(s1, s2[1:], s3[1:])
编辑于 2017-09-16 12:24:48
回复(1)
暴力递归：
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String str1=input.next();
int num1=input.nextInt();
String str2=input.next();
int num2=input.nextInt();
String str3=input.next();
int num3=input.nextInt();
boolean flag;
if(num1+num2==num3){
flag=isContain(str1,str2,str3);
//flag=isContain2(str1,str2,str3,num1,num2,num3);
}
else flag=false;
System.out.println(flag);
}
public static boolean isContain(String str1,String str2, String str3){
return process(str1,str2,str3,0,0,0);
}
public static boolean process(String str1,String str2,String str3,int index1,int index2,int index3){
if(index3>=str3.length()) return true;
boolean flag1=false,flag2=false;
if(index1<str1.length() && str1.charAt(index1)==str3.charAt(index3)){
flag1=process(str1,str2,str3,index1+1,index2,index3+1);
}
if(index2<str2.length() && str2.charAt(index2)==str3.charAt(index3)){
flag2=process(str1,str2,str3,index1,index2+1,index3+1);
}
return flag2||flag2;
} dp做法：
其中dp要考虑到index3=index1+index2;
所以仍然是二维数组，不要用到三维太麻烦了
public boolean chkMixture(String str1, int n, String str2, int m, String str3, int v) {
if(n+m!=v) return false;
boolean[][] dp=new boolean[n+1][m+1];
dp[n][m]=true;
for (int i = n-1; i >=0 ; i--) {
dp[i][m]=str1.charAt(i)==str3.charAt(i+m)? dp[i+1][m]:false;
}
for (int i = m-1; i >=0 ; i--) {
dp[n][i]=str2.charAt(i)==str3.charAt(i+n)? dp[n][i+1]:false;
}
for (int i = n-1; i >=0 ; i--) {
for (int j = m-1; j >=0 ; j--) {
boolean flag1=false,flag2=false;
if(str1.charAt(i)==str3.charAt(i+j)) flag1=dp[i+1][j];
if(str2.charAt(j)==str3.charAt(i+j)) flag2=dp[i][j+1];
dp[i][j]=flag1||flag2;
}
}
return dp[0][0];
}
发表于 2023-08-31 15:33:53
回复(0)
想不明白为什么过不了，哪里出错了吗？
class Mixture:
def chkMixture(self, A, n, B, m, C, v):
pointerA = 0
pointerB = 0
if n+m == v:
for i in range(v):
if pointerA < n and C[i] == A[pointerA]:
pointerA += 1
elif pointerB < m and C[i] == B[pointerB]:
pointerB += 1
else:
return False
return True
else:
return False
if __name__ == "__main__":
A, n, B, m, C, v = eval("["+input().strip()+"]")
print(Mixture().chkMixture(A, n, B, m, C, v))
发表于 2021-09-15 00:37:13
回复(0)
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C, int v) {
if (v != n + m) {
return false;
}
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
if (dp[i - 1][0] && A[i - 1] == C[i - 1]) {
dp[i][0] = true;
}
}
for (int j = 1; j <= m; j++) {
if (dp[0][j - 1] && B[j - 1] == C[j - 1]) {
dp[0][j] = true;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = (dp[i - 1][j] && C[i + j - 1] == A[i - 1])
|| (dp[i][j - 1] && C[i + j - 1] == B[j - 1]);
}
}
return dp[n][m];
}
};
编辑于 2019-04-04 17:53:29
回复(0)
# -*- coding:utf-8 -*- class Mixture: def chkMixture(self, A, n, B, m, C, v): if n == 0 or m == 0 or v == 0:#ABC中任何一个已遍历完毕，则为True return True if A[0] == C[0] and B[0] != C[0]:#C中当前首字符为A的首字符 return self.chkMixture(A[1:], n-1, B, m, C[1:], v-1) if B[0] == C[0] and A[0] != C[0]:#C中当前首字符为B的首字符 return self.chkMixture(A, n, B[1:], m-1, C[1:], v-1) if A[0] == C[0] == B[0]:#C中当前首字符可能为A的首字符，也可能为B的首字符 return self.chkMixture(A[1:], n-1, B, m, C[1:], v-1) or self.chkMixture(A, n, B[1:], m-1, C[1:], v-1)
发表于 2018-08-30 11:41:20
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-09 12:54:12 -
2022-08-27 18:39:56
-
2022-07-30 21:19:37
-
2022-07-28 17:16:56 -
2022-07-05 16:54:38
相关试题
-
评论(110) 来自面试常考算法题(九)-经...
-
评论(53) 来自面试常考算法题(九)-经...
-
评论(108) 来自面试常考算法题(九)-经...
-
评论(74) 来自面试常考算法题(九)-经...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
