A、B和C。如果C包含且仅包含来自A和B的所有字符，而且在C中属于A的字符之间保持原来在A中的顺序，属于B的字符之间保持原来在B中的顺序，那么称C是A和B的混编。实现一个函数，判断C是否是A和B的混编。
给定三个字符串A,B和C，及他们的长度。请返回一个bool值，代表C是否是A和B的混编。保证三个串的长度均小于等于100。
测试样例：
"ABC",3,"12C",3,"A12BCC",6
返回：true
[编程题]字符混编
python递归解法竟然也能通过。。
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:32:01
回复(0)
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;
}
};
前两个判断条件很好理解；关键在于第三个怎么写return，看明白就好，我就不多说了
编辑于 2015-08-06 12:02:55
回复(5)
动态规划：
令D[i][j]代表A中取前i个字符，B中取前j个字符，是否和C中的前i+j个字符交错匹配。
1. 如果i==0 或者j == 0,那么退化为单独的一个字符串是否和C匹配
因此：
D[i][0] = A(i-1) == C(i-1); 1<=i<=A.length
D[0][j] = B(j-1) == C(j-1); 1<=j<=B.length
2. 求D[i][j],分两种情况A[i-1] == C[i+j-1]或者B[j-1] == C[i+j-1]
D[i][j] = D[i-1][j] && A[i-1] == C[i+j-1]
D[i][j] = D[i][j-1] && B[j-1] == C[i+j-1]
因此状态转移方程：
D[i][j] = D[i-1][j] && A[i-1] == C[i+j-1] || D[i][j-1]
&& B[j-1] == C[i+j-1]
public static boolean mixture(String A,String B,String C){
int n = A.length();
int m = B.length();
int v = C.length();
if(m+n != v || v == 0){
return false;
}
//C(i+j) 是否是A(1..i)和B(1..j)的交错字符串
boolean[][] D = new boolean[n+1][m+1];
for(int i = 1; i <= n; i ++){
D[i][0] = A.charAt(i-1) == C.charAt(i-1);
}
for(int j = 1; j <= m ; j ++){
D[0][j] = B.charAt(j-1) == C.charAt(j-1);
}
for(int i = 1; i <= n ; i ++ ){
for(int j = 1; j <= m ; j ++){
D[i][j] = ((A.charAt(i-1) == C.charAt(i+j-1) &&
D[i-1][j])
|| (B.charAt(j-1) == C.charAt(i+j-1) &&
D[i][j-1]));
}
}
return D[n][m];
}
发表于 2015-08-13 12:57:26
回复(0)
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C, int v) {
if(m+n != v || v==0)
return false;
bool dp[n+1][m+1];
dp[0][0] = true;
for(int i=1;i<=n;i++) dp[i][0] = (A[i-1]==C[i-1]); for(int i=1;i<=m;i++) dp[0][i] = (B[i-1]==C[i-1]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j] = ((A[i-1]==C[i+j-1] && dp[i-1][j]) || (B[j-1]==C[i+j-1] && dp[i][j-1])); return dp[n][m];
}
};
发表于 2017-11-01 01:51:56
回复(0)
自我感觉没有用什么算法，只是简单的查找替换，将A，B，遍历一遍，在C中遇见便替换为空（因为可能有重复）
没有遇见直接返回false
- bool chkMixture(string A, int n, string B, int m, string C, int v) {
- // write code here
- if(n+m!=v) return false;
- for(int i = 0;i<n;i++)
- {
- int j = C.find(A[i]);
- if(j==-1) return false;
- else C[j] = ' ';
- }
- for(int i = 0;i<m;i++)
- {
- int j = C.find(B[i]);
- if(j==-1) return false;
- else C[j] = ' ';
- }
- return true;
- }
发表于 2017-08-03 16:30:48
回复(1)
package 字符混编;
/**
* Created by h on 16-12-29.
*/
//很多人写的递归根本就是错的，或者说不够优雅，正确的递归姿势应该是这样的。
public class Mixture {
public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
return chkMixtureHelp(A, B, C);
}
private boolean chkMixtureHelp(String a, String b, String c) {
if (c.equals("") && a.equals("") && b.equals("")) return true;
if (c.equals("")) return false;
char ch = c.charAt(0);
boolean ansOne = false;
boolean ansTwo = false;
if (a.length() > 0 && a.charAt(0) == ch) {
ansOne = chkMixtureHelp(a.substring(1, a.length()), b, c.substring(1, c.length()));
}
if (b.length() > 0 && b.charAt(0) == ch) {
ansTwo = chkMixtureHelp(a, b.substring(1, b.length()), c.substring(1, c.length()));
}
return ansOne || ansTwo;
}
public static void main(String[] args) {
System.out.println(new Mixture().chkMixture("abaacbcababbccccbaababcbbacbaac", 31, "cacbbb", 6, "zjcrmlqwgrsocgnkvafzzeaiixzkmcyqgcmdf", 37));
}
}
编辑于 2016-12-29 12:43:37
回复(0)
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];
for (int i = 1; i<= n; i ++ ) if(A.charAt(i - 1) == C.charAt(i - 1)) dp[i][0] = true;
for (int i = 1; i<= m; i ++ ) if(B.charAt(i - 1) == C.charAt(i - 1)) dp[0][i] = true;
for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) if(C.charAt(i + j - 1) == A.charAt(i - 1) || C.charAt(i + j - 1) == B.charAt(j - 1)) dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
return dp[n][m];
}
}
编辑于 2016-10-18 11:24:37
回复(0)
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 13:57:10
回复(0)
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C, int v) {
if((n+m!=v)||(n==0&&B!=C)||(m==0&&A!=C))
return false;
if((n==0&&B==C)||(m==0&&A==C))
return true;
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(B[0]==C[0]&&A[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-09-05 18:33:05
回复(0)
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C,
int v)
{
int i = 0,j = 0,k = 0;
for(i = 0;i < n;i++)
{
for(j = k;j < v;j++)
{
if(A[i] == C[j])
{
k = j;
break;
}
}
if(j >v-1)
{
return false;
}
}
k = 0;
for(i = 0;i < m;i++)
{
for(j = k;j < v;j++)
{
if(B[i] == C[j])
{
k = j;
break;
}
}
if(j >= v-1)
{
return false;
}
}
return true;
// write code here
}
};
发表于 2016-05-19 11:34:37
回复(0)
import java.util.*;
public class Mixture {
public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
// write code here
//将问题转化成最长公共子序列。设A与C的最长公共子序列长度为n1，B与C的最长公共子序列长度为n2
//如果n1==intn，n2==intm且n1+n2==intv，则返回true，否则返回false。（借用楼上的思路java实现）
int n1=LCS(A,C);
int n2=LCS(B,C);
if(n1==n&&n2==m&&n1+n2==v){
return true;
}else{return false;}
}
public int LCS(String a,String c){
int[][] arr=new int[a.length()+1][c.length()+1];
for(int i=0;i<a.length();i++){
arr[i][0]=0;
}
for(int j=0;j<c.length();j++){
arr[0][j]=0;
}
for(int i=1;i<=a.length();i++){
for(int j=1;j<=c.length();j++){
if(a.charAt(i-1)==c.charAt(j-1)){
arr[i][j]=arr[i-1][j-1]+1;
}else {
if(arr[i-1][j]>=arr[i][j-1]){
arr[i][j]=arr[i-1][j];
}else{
arr[i][j]=arr[i][j-1];
}
}
}
}
return arr[a.length()][c.length()];
}
}
发表于 2015-09-20 22:37:10
回复(0)
因为题目保证三个串的长度均小于等于100，所以直接遍历速度也很快。
classMixture {
public:
bool chkMixture(string A, intn, string B, intm, string C, intv)
{
// write code here
if(n+m != v)
returnfalse;
auto i = 0, j=0;
while(i<n&&j<v){
if(A[i] == C[j]){
i++;
j++;
}
else
j++;
}
if(i<n)
returnfalse;
i = 0, j=0;
while(i<m&&j<v){
if(B[i] == C[j]){
i++;
j++;
}
else
j++;
}
if(i<m)
returnfalse;
returntrue;
}
};
发表于 2015-08-11 14:41:06
回复(0)
将问题转化成最长公共子序列。设A与C的最长公共子序列长度为n1，B与C的最长公共子序列长度为n2
如果n1==intn，n2==intm且n1+n2==intv，则返回true，否则返回false。以下为通过在线测试的代码。
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C, int v) {
// write code here
int len1 = LCS(A, C);
int len2 = LCS(B, C);
return (len1==n && len2==m && v==len1+len2);
}
int LCS(string A, string B) {
int m = A.size(), n = B.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(A[i]==B[j]) dp[i+1][j+1] = dp[i][j] + 1;
else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
}
}
return dp[m][n];
}
};
编辑于 2015-08-09 11:29:35
回复(0)
//这种题还是需要dp数组从1开始算，可省去很多边界处理问题
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C, int v) {
// write code here
bool dp[101][101]={false};
memset(dp,0,sizeof(bool)*101*101);
dp[0][0] = true;
for(unsigned int i = 1 ; i <= A.length() ;i++)
dp[i][0] = A[i-1] == C[i-1] && dp[i-1][0];
for(unsigned int i = 1 ; i <= B.length() ;i++)
dp[0][i] = B[i-1] == C[i-1] && dp[0][i-1];
for(unsigned int i = 1 ; i <= A.length() ; i++)
{
for(unsigned int j = 1 ; j <= B.length() ; j++)
{
dp[i][j] = (dp[i-1][j] && (A[i-1] == C[i+j-1])) || (dp[i][j-1] && (B[j-1] == C[i+j-1]));
}
}
return dp[A.length()][B.length()];
}
};
发表于 2017-09-06 16:26:13
回复(0)
我是个铁憨憨，竟然用了个三位数组来做。
import java.util.*;
public class Mixture {
public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
// write code here
if (n + m > v) {
return false;
}
boolean[][][] dp = new boolean[n + 1][m + 1][v + 1];
for (int i = 0; i <= v; ++i) {
dp[0][0][i] = true;
}
for (int i = 1; i <= m; ++i) {
for (int j = i; j <= v; ++j) {
dp[0][i][j] = dp[0][i][j - 1] || (dp[0][i - 1][j - 1] && B.charAt(i - 1) == C.charAt(j - 1));
}
}
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= v; ++j) {
dp[i][0][j] = dp[i][0][j - 1] || (dp[i - 1][0][j - 1] && A.charAt(i - 1) == C.charAt(j - 1));
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= v; ++k) {
dp[i][j][k] = dp[i][j][k - 1] || (dp[i - 1][j][k - 1] && A.charAt(i - 1) == C.charAt(k - 1)) || (dp[i][j - 1][k - 1] && B.charAt(j - 1) == C.charAt(k - 1));
}
}
}
return dp[n][m][v];
}
}
发表于 2020-03-02 20:43:10
回复(0)
当遇到了A中可以和C当前匹配，B中也可以，此时不知道是和A还是和B去匹配。使用递归的方式，当遇到上面的问题的时候，会有重叠子问题，dp则没有。答案中基本上都是dp的做法，我贴以下递归的做法，本人水平有限写出来不太够优雅
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C, int v) {
if(n + m != v) return false;
return chkMixture_recu(A, 0, n, B, 0, m, C, 0, v);
}
bool chkMixture_recu(string A, int pos1, int n, string B, int pos2, int m, string C, int pos3, int v) {
if(pos1 == n && pos2 == m && pos3 == v) return true;
if(pos1 < n && pos2 < m && pos3 < v && A[pos1] == B[pos2] && A[pos1] == C[pos3]{ return (chkMixture_recu(A, pos1 + 1, n, B, pos2, m, C, pos3 + 1, v) || chkMixture_recu(A, pos1, n, B, pos2 + 1, m, C, pos3 + 1, v));
}else if(pos1 < n && pos3 < v && A[pos1] == C[pos3]){
return chkMixture_recu(A, pos1 + 1, n, B, pos2, m, C, pos3 + 1, v);
}else if(pos2 < m && pos2 < v && B[pos2] == C[pos3]) {
return chkMixture_recu(A, pos1, n, B, pos2 + 1, m, C, pos3 + 1, v);
}else {
return false;
}
}
};
编辑于 2019-07-21 12:16:29
回复(0)
# -*- coding:utf-8 -*- class Mixture: def chkMixture(self, A, n, B, m, C, v): while n!=0 and m!=0 and v!=0:#某一串已遍历完 a,b,c=A[0],B[0],C[0] if c==a and c==b:#A、B、C首字母相等 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) elif c==a:#A、C首字母相等 return self.chkMixture(A[1:],n-1,B,m,C[1:],v-1) elif c==b:#A、B首字母相等 return self.chkMixture(A,n,B[1:],m-1,C[1:],v-1) else: return False return True
发表于 2018-09-12 12:12:31
回复(0)
不用动态规划，容易理解
public boolean chkMixture(String A, int n, String B, int m, String C, int v) { if(n+m>v) return false;
int dp1=0;
int dp2=0;
int index1=0;
int index2=0;
for(int i=0;i<v&&index1<n;i++) {
if(C.charAt(i)==A.charAt(index1)) {
index1++;
dp1++;
}
}
for(int i=0;i<v&&index2<m;i++) {
if(B.charAt(index2)==C.charAt(i)) {
index2++;
dp2++;
}
}
// // System.out.println(dp1);
// System.out.println(dp2);
return dp1==n&&dp2==m;
}
发表于 2018-06-10 14:33:16
回复(0)
class Mixture {
public:
bool core(string& s1,string& s2,int n,int m)
{
vector<vector<int>> co(n+1,vector<int>(m+1,0));
for(int i=0;i<=n;i++)
{
if(s1[i]==s2[0])
co[i][0]=1;
}
for(int i=0;i<=m;i++)
{
if(s2[i]==s1[0])
co[0][i]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s1[i]==s2[j])
{
co[i][j]=co[i-1][j-1]+1;
if(co[i][j]==m)
return true;
}
else
co[i][j]=max(co[i-1][j],co[i][j-1]);
}
}
return co[n][m]==m;
}
bool chkMixture(string A, int n, string B, int m, string C, int v) {
// write code here
return core(C,A,v,n)&&core(C,B,v,m);
}
};
//////////////////////////////////////////////////
class Mixture {
public:
bool chkMixture(string A, int n, string B, int m, string C, int v) {
// write code here
vector<vector<bool>> co(n+1,vector<bool>(m+1,false));
co[0][0]=true;
for(int i=1;i<=n;i++)
{
if(A[i-1]==C[i-1])
co[i][0]=true;
}
for(int i=1;i<=m;i++)
{
if(B[i-1]==C[i-1])
co[0][i]=true;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!co[i][j])
{
if(co[i][j-1]&&(B[j-1]==C[i+j-1]))
co[i][j]=true;
if(co[i-1][j]&&(A[i-1]==C[i+j-1]))
co[i][j]=true;
}
}
}
return co[n][m];
}
};
编辑于 2018-05-24 08:37:14
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-30 15:22:05
-
2022-08-27 18:41:00
-
2022-08-25 17:50:38 -
2022-07-28 17:18:27 -
2022-07-05 22:58:12
相关试题
-
评论(100) 来自面试常考算法题(十)-经...
-
评论(44) 来自面试常考算法题(十)-经...
-
评论(19) 来自面试常考算法题(十)-经...
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
未了方便处理，在A和B的前面添加一个空字符。dp的初始化如下图
下面就开始找dp的状态转移方程了
dp[i][j]就表示 A[0 ~ i-1]和B[0 ~ j-1]是否构成C[ 0 ~ i+j-1]
dp[i][j]=true的第二种情况是
dp绘制完成后，如下图所示
只要dp[n][m] = true,结果就是true
其中n为A字符串的长度，m为B字符串的长度。
整体代码如下
import java.util.*; public class Mixture { public boolean chkMixture(String A, int n, String B, int m, String C, int v) { // 边界情况处理 if (m + n != v) return false; // 默认初始化为false boolean[][] dp = new boolean[101][101]; dp[0][0] = true; // 初始化第0行 for (int i = 1; i <= m; ++i) { if (B.charAt(i - 1) == C.charAt(i - 1)) dp[0][i] = true; else break; } // 初始化第0列 for (int i = 1; i <= n; ++i) { if (A.charAt(i - 1) == C.charAt(i - 1)) dp[i][0] = true; else break; } /* * 状态转移方程 * dp[i][j] = * * case 1: dp[i][j-1] == true && B[j-1] == C[i+j-1] * * case 2: dp[i-1][j] == true && A[i-1] == C[i+j-1] * */ for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (!dp[i][j]) { // dp[i-1][j] = true && A[i-1] == C[i+j-1] if (dp[i - 1][j] && A.charAt(i - 1) == C.charAt(i + j - 1)) dp[i][j] = true; // dp[i][j-1] == true && B[j-1] == C[i+j-1] if (dp[i][j - 1] && B.charAt(j - 1) == C.charAt(i + j - 1)) dp[i][j] = true; } } } return dp[n][m]; } }上的代码使用了额外的空间，时间复杂度为O(n^2)虽然没有递归调用代码简洁，但是如果每个字符串的长度过长时，递归容易出现栈溢出。