首页 > 试题广场 >

字符串字符匹配

[编程题]字符串字符匹配
  • 热度指数:158044 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
判断短字符串S中的所有字符是否在长字符串T中全部出现。
请注意本题有多组样例输入。
数据范围:
进阶:时间复杂度:,空间复杂度:

输入描述:

输入两个字符串。第一个为短字符串,第二个为长字符串。两个字符串均由小写字母组成。



输出描述:

如果短字符串的所有字符均在长字符串中出现过,则输出字符串"true"。否则输出字符串"false"。

示例1

输入

bc
abc

输出

true

说明

其中abc含有bc,输出"true"
 
import java.util.HashMap;
/* 判断短字符串中的所有字符是否在长字符串中全部出现
 * 遍历长字符串,统计各个字符出现的频率
 * 遍历短字符串的各个字符,在长字符该字符下频率是否为0,如果有为0的就说明不是全部存在,全部不为0,就是全部存在
 * */
import java.util.Scanner;
public class Main {
	public static boolean isAllCharExist(String shortString, String longString){
		int[] bucket = new int[128];
		for (int i = 0; i < longString.length(); i++)  //桶 统计频率,某个字符出现频率不为0
			bucket[longString.charAt(i)]++;
		for (int i = 0; i < shortString.length(); i++) {  //短字符串各个字符在长字符串各个字符频率情况
			if(bucket[shortString.charAt(i)] == 0)
				return false;
		}
		return true;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			String strShort = sc.nextLine();
			String strLong = sc.nextLine();
			System.out.println(isAllCharExists(strShort, strLong));
		}
	}
}


发表于 2017-06-17 16:17:11 回复(3)
可以首先把长字符串中的每个字符依次放进map里面并且令其值为1,然后对短字符串中每个字符串看看对应的map是不是为1,如果不是直接退出返回false,短字符串中的每个字符对应的map值都为1返回true。算法复杂度为线性。
#include<iostream>
#include<string>
#include<map>
using namespace std;
bool IsAllCharExist(string str1,string str2)
{
    int len1=str1.size(),len2=str2.size();
    map<char,int>map;
    for(int i=0;i<len2;++i)
        map[str2[i]]=1;
    for(int i=0;i<len1;++i)
        if(map[str1[i]]!=1)return false;
    return true;
}
int main()
{
    string str1,str2;
    while(cin>>str1>>str2)
    {
        if(IsAllCharExist(str1,str2))cout<<"true"<<endl;
        else cout<<"false"<<endl;
    }
    return 0;
}

发表于 2016-08-12 09:58:27 回复(3)
//思路:判断s1中的每个字符是否都在s2中
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        bool flag=true;
		for(int i=0; i<s1.size(); i++){
            if(s2.find(s1[i])==-1){
                cout<<"false"<<endl;
                flag=false;
                break;
            }          
        }
        if(flag)
        cout<<"true"<<endl;
    }
    return 0;
}

发表于 2016-10-06 21:52:56 回复(3)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner jin = new Scanner(System.in);
        while(jin.hasNextLine()) {
        	String sh = jin.nextLine();
        	String lo = jin.nextLine();
        	System.out.println(isMatch(sh, lo));
        }
    }
    public static boolean isMatch(String sh, String lo) {
    	for(int i = 0; i < sh.length(); i++) {
    		if(!lo.contains(Character.toString(sh.charAt(i))))
    			return false;
    	}
    	return true;
    }
}

发表于 2016-08-29 18:52:49 回复(5)
//多定义一个字符串flag,第一个字符串中有与第二个字符串相同的字符时,
//将flag中相应的字符置为‘a’或其他都可以,最后判断flag与第一个字符串长度是否相同
#include<stdio.h>
#include<string.h>
int main()
{
    char duan[100];
    while(gets(duan)!=NULL)
    {char chang[100];
    char flag[100]={0};
		gets(chang);
	int i,j;
    for(i=0;i<strlen(duan);i++)
    {
        for(j=0;j<strlen(chang);j++)
        {
            if(duan[i]==chang[j])
                flag[i]='a';
        }
    }
    if(strlen(duan)==strlen(flag))
        printf("true\n");
    else printf("false\n");
	}
}

发表于 2017-05-08 11:39:09 回复(3)
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main() {//第一次看成KMP了,算半天提交出错
	string str1, str2;
	while (cin >> str1 >> str2) {
		vector<bool> helper(26, false);
		bool flag = true;
		for (auto s : str2) helper[s - 'a'] = true;
		for (auto s : str1) 
			if (!helper[s - 'a']) {
				flag = false; break;
			}
		if (flag) cout << "true" << endl;
		else cout << "false" << endl;
	}
}

发表于 2017-03-19 17:35:39 回复(3)

思路:

题目中说字符匹配,案例中给的全是小写字符,因此就假定只会出现小写字符吧(就算出现别的也一样),因此可以将每个字符当做一个位置索引,建立一个数组arr[26](26是因为假设只有小写字母)并初始化全0,当出现某个字符s时,只需要将arr['s'-'a']位置加1即可。这样未出现过的字符的位置为0,出现过字符位置不为0。

代码:

#include<iostream>
#include<string>
using namespace std;

int main()
{
    string shortStr, longStr;
    while(cin >> shortStr >> longStr)
    {
        bool flag = true;
        int arr[26] = {0};
        for(int i = 0; i < longStr.length(); i++)
            arr[longStr[i]-'a']++;            //记录出现的字符
        for(int i = 0; i < shortStr.length(); i++)
        {
            if(!arr[shortStr[i]-'a'])
            {
                flag = false;
                break;
            }
        }
        cout << (flag? "true":"false") << endl;
    }
    return 0;
}


编辑于 2020-07-20 18:09:23 回复(1)
#include<string>
(765)#include<iostream>
#include<stdlib.h>
using namespace std;

string  String_matching(string &str1, string &str2)
{
	// 判断短字符串中的所有字符是否在长字符串中出现
	for (int i = 0; i < str1.size(); i++)
	{
		if (str2.find(str1[i], 0) == string::npos)
		{
			return "false";
		}
	}
	return "true";
}

int main()
{
	string str1,str2;
	while (cin >> str1 >> str2)
	{
		string ans = String_matching(str1, str2);
		cout << ans << endl;
	}
	system("pause");
	return 0;
}

发表于 2020-03-07 16:23:38 回复(0)

解决方法:使用将长字符串放入unordered_set中,然后遍历段字符串寻找是否存在。
时间复杂度:O(s) + O(l) s:短字符串长度 l:长字符串长度

#include <string>
#include <iostream>
#include <unordered_set>

using namespace std;
int main(){
    string a, b;
    while(cin >> b >> a){//b为短字符串 a为长字符串
        bool ans = true;
        unordered_set<char> sa(a.begin(), a.end());
        for(char c : b){
            if(sa.find(c) == sa.end()){
                ans = false;
                break;
            }
        }
        if(ans) cout << "true" << endl;
        else cout << "false" << endl;
    }
    return 0;
}
发表于 2019-03-12 14:51:58 回复(2)
/*  
*** 本代码思路比较简单:char[]数组存放短字符串,遍历char[]数组,并使用string.contains()
*   方法判断长字符串是否含有短字符,如果全都含有,则打印true,判断过程中不含有某个短字符
*   ,则打印false,并break;
*/
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            char[] shortChar = sc.nextLine().toCharArray();
            String str = sc.nextLine();
            for(int i=0;i<shortChar.length;i++){
                if(!str.contains(String.valueOf(shortChar[i]))){
                    System.out.println("false");
                    break;
                }
                if(i == shortChar.length-1){
                    System.out.println("true");
                }
            }
        }
    }
}

发表于 2018-10-17 19:39:19 回复(0)
import java.util.Scanner;
import java.util.HashSet;

public class ShortLongString {

    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        while(in.hasNext()){
            String shortone= in.nextLine();
            String longone =in.nextLine();
            StringBuffer sb =new StringBuffer(longone);
            HashSet<String> hs =new HashSet<String>();
            for(int i=0;i<sb.length();i++){
                hs.add(sb.substring(i,i+1));
            }
            boolean result =true;
            for(int j=0;j<shortone.length();j++){
                if(hs.add(shortone.substring(j,j+1))){
                    result =false;
                    break;
                }
            }
            System.out.println(result);
        }

    }

}
发表于 2018-03-22 15:10:04 回复(0)
s1 = input()
s2 = input()
for x in s1:
    if x not in s2:
        print('false')
        break
else:
    print('true')

发表于 2022-07-29 23:04:40 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String  shortS = br.readLine();
        String longS = br.readLine();
        int[] l = new int[26];
        for(char c : longS.toCharArray()){
            l[c-'a']++;
        }
        for(char c : shortS.toCharArray()){
            if(l[c-'a']==0){
                System.out.println(false);
                return;
            }
        }
        System.out.println(true);


    }
}
因为是小写字母,所以直接用数组来保存就行

发表于 2022-07-28 22:32:13 回复(0)
import java.util.*;
public class Main {
    public static void main(String[] args){
        // 接收输入字符串
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            // 将短字符串截成数组
            String strs =  input.nextLine();
            String strk = input.nextLine();
            boolean bool = true;
            for (int i = 0; i < strs.length(); i++) {
                if(!strk.contains(String.valueOf(strs.charAt(i)))){
                    // 出现一次不包含就结束循环并返回false
                    bool = false;
                    break;
                }
            }
            System.out.println(bool);
        }
    }
}
发表于 2022-04-14 15:31:15 回复(0)
简单易懂!很好奇为啥这道题的难度是较难?没提交之前我还怀疑是不是写错了呢🤣
def judge(str1,str2):
    for i in str1:
        if i not in str2:
            return False
    else:
        return True
while True:
    try:
        str1=input()
        str2=input()
        a=judge(str1, str2)
        if a:
            print("true")
        else:
            print("false")
    except:
        break
发表于 2022-01-04 15:50:45 回复(0)
python3使用str.maketrans取交集
while True:
 try:
  a,b=input(),input()
  print ("true" if a.translate(str.maketrans('','',b))=='' else "false")
 except:break

发表于 2021-11-23 17:07:35 回复(0)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            String l = sc.nextLine();
            System.out.println(match(s, l));
        }
    }

    // 匹配短串字符是否出现在长串(不需按顺序)
    public static boolean match(String s, String l) {
        out : for (int i=0; i<s.length(); i++) {
            for (int j=0; j<l.length(); j++) {
                if (s.charAt(i) == l.charAt(j)) {
                    if (i == s.length()-1) {
                        break out;
                    }
                    continue out;
                }
            }
            return false;
        }
        return true;
    }
}

发表于 2021-11-08 15:08:30 回复(0)
while True:
    try :
        a = input()
        b = input()

        for i in a:
            if i in b:
                flag = "true"
                continue
            else:
                flag = "false"
                break

        print(flag)
    except:
        break

发表于 2021-09-16 21:39:51 回复(0)
##简单实现
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()){
            String s =in.nextLine();
            String l =in.nextLine();
            boolean flag = true;
            for(int i=0;i<s.length();i++){
                if(l.contains(String.valueOf(s.charAt(i)))){
                    continue;
                } else {
                    flag = false;
                }
            }
            System.out.println(flag);
        }
    }
}

发表于 2021-09-13 00:12:49 回复(0)
运行时间:4ms超过24.25% 用C++提交的代码
占用内存:460KB超过72.33%用C++提交的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b;
    while(cin>>a>>b){
        string f = "true";
        for(int i = 0;i<a.size();i++){
            if(b.find(a[i])==-1){
              f = "false";
               break;}
            }
        cout<<f<<endl;
    }
}



发表于 2021-08-17 10:08:42 回复(0)