首页 > 试题广场 >

字符串的交错组成

[编程题]字符串的交错组成
  • 热度指数：2073 时间限制：C/C++ 4秒，其他语言8秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定三个字符串str1、str2 和aim,如果aim包含且仅包含来自str1和str2的所有字符，而且在aim中属于str1的字符之间保持原来在str1中的顺序属于str2的字符之间保持原来在str2中的顺序，那么称aim是str1和str2的交错组成。实现一个函数，判断aim是否是str1和str2交错组成，如果是请输出“YES”，否则输出“NO”。


输入描述:
输出三行，分别表示三个字符串str1，str2和aim。 ， 表示字符串长度。


输出描述:
输出“YES”或者“NO”。（不包含引号）
示例1

输入

AB
12
1AB2

输出

YES
示例2

输入

2019
9102
22001199

输出

NO

备注:
时间复杂度,空间复杂度。（n表示字符串str1长度，m表示s字符串tr2长度）
算法知识视频讲解
添加回答
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s1,s2,aim;
    cin>>s1>>s2>>aim;
    if (aim.size() != s1.size() + s2.size())
    {
        cout<< "NO";
        return 0;
    }
    string ls = s1.size() >= s2.size() ? s1 : s2;
	string ss = s1.size() < s2.size() ? s1 : s2;
	vector<bool>dp(ss.size() + 1);
	dp[0] = true;
	for (int i = 1; i <= ss.size(); i++){
		if (ss[i - 1] != aim[i - 1])
			break;
		dp[i] = true;
	}
	for (int i = 1; i <= ls.size(); i++){
		dp[0] = dp[0] && ls[i - 1] == aim[i - 1];
		for (int j = 1; j <= ss.size(); j++){
			if ((ls[i - 1] == aim[i + j - 1] && dp[j]) || (ss[j - 1] == aim[i + j - 1] && dp[j - 1]))
				dp[j] = true;
			else
				dp[j] = false;
		}
	}
    if(dp[ss.size()])
	    cout<< "YES";
    else
        cout<< "NO";
    return 0;
}

发表于 2019-08-31 21:22:57 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

bool F(string s, string aim){
    int n = s.length(), m = aim.length();
    for(int i=0,j=0;i<n;){
        if(s[i]==aim[j]){
            i++;
            j++;
        }else
            j++;
        if(j==m && i<n)
            return false;
    }
    return true;
}

int main(){
    string s1, s2, aim;
    cin>>s1>>s2>>aim;
    if(F(s1, aim) && F(s2, aim))
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}

发表于 2020-03-05 00:13:22 回复(2)
Java
habitplus头像 habitplus
这题的后台用例应该全是出现 len(str1) + len(str2) == len(aim) && aim 的字符刚好全是来自 str1 和 str2，所以分别判断 str1 与 str2 的在 aim 中的出现顺序是否一致即可
发表于 2021-09-13 15:32:44 回复(0)
C/C++
花下卿舞袖头像 花下卿舞袖
其实是水题，我的出发点错了，开始想着两两匹配，结果出现各种恶心情况，后来和师兄讨论被一语点醒：三个一起匹配。。。。。。
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main(){
    string str1,str2,aim;
    int flag = 0,s1 = 0,s2 = 0,a = 0;
    getline(cin,str1);
    getline(cin,str2);
    getline(cin,aim);
    while((s1<str1.length()||s2<str2.length())&&a<aim.length()){
        if(aim[a]==str1[s1]){
            s1++;
            //flag = 1;
        }
            
        if(aim[a]==str2[s2]){
            s2++;
            //flag = 1;
        }
            a++;
    }
    if(s1==str1.length()&&s2==str2.length()&&a == aim.length()){
        cout<<"YES";
    }
    else
        cout<<"NO";
}


编辑于 2020-10-12 11:18:22 回复(0)
Java
0OFFER救救我头像 0OFFER救救我 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        String s3 = sc.nextLine();
        int a = s1.length(), b = s2.length(), c = s3.length();
        if (a + b != c) {
            System.out.print("NO");
        } else if (func(s1, s2, s3)) {
            System.out.print("YES");
        } else {
            System.out.print("NO");
        }
    }
    public static boolean func(String s1, String s2, String s3) {
        boolean[][] f = new boolean[s1.length() + 1][s2.length() + 1];
        f[0][0] = true;
        for (int i = 1; i <= s1.length(); i++) {
            if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
                f[i][0] = true;
            } else {
                break;
            }
        }
        for (int j = 1; j <= s2.length(); j++) {
            if (s2.charAt(j - 1) == s3.charAt(j - 1)) {
                f[0][j] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                f[i][j] = (f[i -1][j] == true && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (f[i][j -1] == true && s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        return f[s1.length()][s2.length()];
    }
}
java 100%

发表于 2020-08-24 00:21:01 回复(0)
牛客512196961号头像 牛客512196961号
这个用例输入有问题？没有str2？

链接：https://www.nowcoder.com/questionTerminal/1fdefa4178f7460d93738b28441e1277
来源：牛客网
用例:
xkaerlabocboywvcdnduuvbvgzbwqgemrjlaweexrfquwdqpmsdiulzajtakkndgnqwcdzhjknukzvdrvdndjwbarpeacxmiwdrnawyagilbekhdwqdbmmsgudqjakeyafltdciqsepuszkqipvmmwhdvxansblqtmtkwnqchzsijngupfivpdkwjoohqrbhdubqrjyydyhedmyqbskwgbhqektnralgfctlicgzwdawpdowuqpsaisspbsbqnxmbunodomlicxhsuabxtvqrbktrnlvsubmtcgiawdnrvlbjrwrvflfwdbvvqgobxaausdyrzaqfuoyfcfzguquqifxbiywpuqwfmzootnswhxfedfodeisrdbqvtlxnbnbwjbbdtyousydgkudltvkbgijgjjnkgsdnavkhjfozavckzetsnxkftudjjudvibvrfzglvbjstnarjzgldrvwyrvibntizjcdlmsubsdyncoawgjcdfqtnpwyovzomcvuspeupknyezadpsswnlcjsqfyxcxkwelbeedjjcmiomtixqfgjvgsnemwaummpgoetzdacrdcvnolkynuzrvalzqnpbgdjmjzfreiqhxhtfoisubjbqqisftafwaxehobagttaqaescqfmnemdjufcmrpkjkmsvmpjwtqtjxmucbrlplbglzjlmttrghfgyzeeslubsgeawmhzwayuuitdiaryosuapkqomkfkxiiipxadntmlcpkqfifqestqykzwekczqhqjotibsbfnneqgvipnakgntddajtulyknchvivugjiwcosgaczmxgzppyazsdiuqiaoymfltgcmgtfxxfcheesflcahzwpktvqhjxnfhdtdmjnmtpwltqwcvfifhvqgakwqjkvxeqdhbalpldqcpfcicftvtvjsbwlaztrzuukoxpxkebyedkohnutwermlprcxoflcywbpljrsirtqsnmjxxmavfdtanrvpmqgmfen
发表于 2020-07-10 00:23:53 回复(0)
我要收offer头像 我要收offer 
import java.io.*;
/**
此题是考察递归转化为动态规划。
如果能够想到aim的最后一个字符必须要和str1、str2中的一个字符串的最后一个字符相同的话就可以很容易写出递归。
此时递归形如helper(char[] str1, i1, char[] str2, i2), 表示判断str1中索引i1及以前的字符与str2中i2及以前的字符能否交错组成aim中索引i1+i2+1及以前的字符。
这时就能够容易看出如何设置dp数组，dp[i][j]与dp[i-1][j]和dp[i][j-1]相关。
再转化为一维的dp即可。
*/
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        char[] arr1 = bf.readLine().toCharArray();
        char[] arr2 = bf.readLine().toCharArray();
        char[] aim = bf.readLine().toCharArray();
        bf.close();
        
        if (aim.length != arr1.length + arr2.length) {
            System.out.println("NO");
        } else if (helper(arr1, arr2, aim)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }

    }

    public static boolean helper(char[] arr1, char[] arr2, char[] aim) {

        char[] temp;
        if (arr2.length > arr1.length) {
            temp = arr2;
            arr2 = arr1;
            arr1 = temp;
        }
        boolean dp[] = new boolean[arr2.length + 1];
        dp[0] = true;
        for (int i = 1; i < arr2.length + 1; i++) {
            dp[i] = aim[i - 1] == arr2[i - 1] && dp[i - 1];
        }
        for (int i = 1; i < arr1.length + 1; i++) {
            for (int j = 0; j < arr2.length + 1; j++) {
                if (j == 0) {
                    dp[0] = dp[0] && arr1[i - 1] == aim[i - 1];
                } else {
                    dp[j] = (arr1[i - 1] == aim[i + j - 1] && dp[j]) || (arr2[j - 1] == aim[i + j - 1] && dp[j - 1]);
                }
            }
        }
        return dp[arr2.length];
    }
}

发表于 2020-06-07 23:12:33 回复(0)
提交观点

问题信息

模拟
上传者：小小
难度：
7条回答 2152浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号