首页 > 试题广场 >

构建短字符串

[编程题]构建短字符串
  • 热度指数：4489 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
给定任意一个较短的子串，和另一个较长的字符串，判断短的字符串是否能够由长字符串中的字符构建出来，且长串中的每个字符只能用一次。

输入描述:
一行数据包括一个较短的字符串S和一个较长的字符串T，用一个空格分隔。保证1<=|S|<=|T|<=100000。


输出描述:
如果短的字符串可以由长字符串中的字符构建出来，输出字符串 “true”，否则输出字符串 "false"。
示例1

输入

a b

输出

false
示例2

输入

fj jfiejfiejfie

输出

true
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s, t;
    cin>>s>>t;
    int a[26] = {0}, b[26] = {0};
    for(int i=0;i<s.length();i++)
        a[s[i]-'a']++;
    for(int i=0;i<t.length();i++)
        b[t[i]-'a']++;
    bool flag = true;
    for(int i=0;i<26;i++){
        if(a[i]>b[i]){
            flag = false;
            break;
        }
    }
    cout<<(flag?"true":"false")<<endl;
    return 0;
}

发表于 2019-07-13 02:47:01 回复(0)
更多回答
Python
ElonB头像 ElonB 
""""
一种借助字典的思路，时间复杂度较低
"""
from collections import Counter

if __name__ == "__main__":
    s, t = map(dict, map(Counter, input().strip().split()))
    flag = True
    for c in s.keys():
        if c not in t.keys() or s[c] > t[c]:
            flag = False
            break
    print("true" if flag else "false")

发表于 2019-07-13 15:15:14 回复(0)
无心2019头像 无心2019 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    map<char,int> m;   
    bool flag = true;   //用来判断能不能构建短字符串
    for(auto it : t)
        m[it]++;
    for(auto it : s)
    {
        if(m[it])
            m[it]--;
        else
            flag = false;
    }
    if(flag)
        cout<<"true";
    else
        cout<<"false";
    return 0;
}

发表于 2019-07-03 22:20:27 回复(0)
Java
谁的电脑头像 谁的电脑 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        String t = scanner.next();
        int[] chs = new int[26];
        for (int i = 0; i < t.length(); i++) {
            chs[t.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            chs[s.charAt(i) - 'a']--;
        }
        for (int i : chs) {
            if (i < 0) {
                System.out.println("false");
                return;
            }
        }
        System.out.println("true");
    }
}
编辑于 2019-07-08 17:01:30 回复(1)
C/C++
昔遥暮云头像 昔遥暮云 
#include <bits/stdc++.h>
using namespace std;
int main(){
    string str;
    bool flag=true;
    int vis[26]={0};
    cin>>str;
    cin.ignore();
    char c;
    while((c=cin.get())!='\n'){
        vis[c-97]++;
    }
    for(int i=0;i<str.size();i++){
        if(vis[str[i]-97]==0){
            flag=false;
            break;
        }
        else
            vis[str[i]-97]--;
    }
    cout<<(flag ? "true":"false");
    return 0;
}

发表于 2019-10-09 20:54:32 回复(0)
C
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
#include <stdio.h>
#include <stdlib.h>

int main(void) {
  char s[100000] = "", t[100000] = "";
  scanf("%s %s", s, t);
  
  int counts[26] = { 0 };
  
  const char* p = t;
  while (*p) ++counts[*p++ - 97];
  
  p = s;
  while (*p) --counts[*p++ - 97];
  
  int i;
  for (i = 0; i < 26; ++i)
    if (counts[i] < 0)
      return puts("false"), 0;
  
  return puts("true"), 0;
}

发表于 2021-07-21 19:11:03 回复(0)
Java
lmz9509头像 lmz9509 
/*
我的想法是，每次把短字符串的字符拿出来在长字符串里找对应的字符，
如果找到结尾都成立则返回true，否则返回false
*/

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String shortstr = input.next();
        String longstr = input.next();
        StringBuffer sb = new StringBuffer();
        sb.append(longstr);//将长字符串放到sb中容易修改
        for(int i = 0;i<shortstr.length();i++){
            String s = String.valueOf(shortstr.charAt(i));//为了可以使用indexOf(String str)
            if(sb.indexOf(s)!=-1)
                sb.setCharAt(sb.indexOf(s),' ');//将已经使用的位置赋值为空格，防止二次使用
            else{
                System.out.println(false);
                return;
            }
        }
        
        System.out.println(true);
    }
}
比较笨拙的方法，不喜勿喷
发表于 2020-04-27 14:38:14 回复(0)
初心者托奇头像 初心者托奇 
from collections import Counter
a = list(map(Counter,input().split()))
print('false' if [0 for i in a[0] if a[0][i] > a[1][i]] else 'true')

编辑于 2020-03-17 11:52:31 回复(0)
lentolove头像 lentolove 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Solution6_构建短字符串 {

    /**
     * 思路一：
     * 1.将长字符串的添加到HashMap中,字符和出现的次数
     * 2.遍历较短的字符串，如果map中不包含该字符，则直接输出false，return；
     * 否通将map出现的字符的个数减一，知道遍历完较短的字符串 输出 true；
     */
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = bf.readLine().split(" ");
        if (line1[0].length() > line1[1].length()) {
            System.out.println(false);
            return;
        }
        HashMap<Character, Integer> t_map = new HashMap<>();//较长字符串
        for (Character c : line1[1].toCharArray()) {
            t_map.put(c, t_map.getOrDefault(c, 0) + 1);
        }
        for (Character c : line1[0].toCharArray()) {
            if (t_map.containsKey(c) && t_map.get(c) > 0) {
                t_map.put(c, t_map.getOrDefault(c, 0) - 1);
            } else {
                System.out.println(false);
                return;
            }
        }
        System.out.println(true);
    }
}

public class Main {

    /**
     * 思路二：借助数组实现hashmap
     */
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = bf.readLine().split(" ");
        if (line1[0].length() > line1[1].length()) {
            System.out.println(false);
            return;
        }
        //直接将26个字符保存在数组中，nums[0] 表示 a,nums[1] 表示b
        int[] nums = new int[26];
        for (int i = 0; i < line1[1].length(); i++) {
            nums[line1[1].charAt(i) - 'a']++;
        }
        //遍历较短字符串
        for (int i = 0; i < line1[0].length(); i++) {
            int x = line1[0].charAt(i) - 'a';
            if (nums[x] > 0) {
                nums[x]--;
            }else {
                System.out.println(false);
                return;
            }
        }
        System.out.println(true);
    }
}
发表于 2019-07-28 14:52:46 回复(1)
pein531头像 pein531
用哈希表分别对两个字符串进行wordCount，只有对S中的任意字符，T中的字符数量都不少于S中的数量才能在不重复使用字符的情况下用T中的字符构建出S。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().trim().split(" ");
        System.out.println(solve(strs[0].toCharArray(), strs[1].toCharArray()));
    }
    
    private static boolean solve(char[] S, char[] T) {
        HashMap<Character, Integer> counter1 = new HashMap<>();
        HashMap<Character, Integer> counter2 = new HashMap<>();
        for(int i = 0; i < T.length; i++){
            if(i < S.length){
                if(counter1.containsKey(S[i]))
                    counter1.put(S[i], counter1.get(S[i]) + 1);
                else
                    counter1.put(S[i], 1);
            }
            if(counter2.containsKey(T[i]))
                counter2.put(T[i], counter2.get(T[i]) + 1);
            else
                counter2.put(T[i], 1);
        }
        for(Character key: counter1.keySet())
            if(!counter2.containsKey(key) || counter1.get(key) > counter2.get(key)) return false;
        return true;
    }
}


发表于 2021-02-27 15:28:00 回复(0)
Python3
TS9527头像 TS9527
用哈希记录长串中各字符出现次数，然后对比短串中各字符出现次数就行，都小于等于才输出true，否则输出false 

class MainActivity:

    def main(self):
        # Read the data
        shortS, longS = filter(lambda x: len(x) > 0, input().split(' '))
        # Initialization
        charCnt = dict()
        # Traverse
        for char in longS:
            charCnt[char] = charCnt.get(char, 0) + 1
        # Check
        for char in shortS:
            if char in charCnt and charCnt[char]:
                charCnt[char] -= 1
            else:
                print('false')
                return
        print('true')


if __name__ == '__main__':
    M = MainActivity()
    M.main()
发表于 2024-08-27 00:54:18 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var s1,s2 string
    fmt.Fscan(in,&s1,&s2)
    cnt:=map[byte]int{}
    for _,ch:=range []byte(s2){
        cnt[ch]++
    }
    for _,ch:=range []byte(s1){
        if _,ok:=cnt[ch];!ok{
            fmt.Print(false)
            return
        }else{
            cnt[ch]--
            if cnt[ch]==0{
                delete(cnt,ch)
            }
        }
    }
    fmt.Print(true)
}

发表于 2023-03-21 14:49:33 回复(0)
C++
Hank丶涵头像 Hank丶涵 
#include <bits/stdc++.h>
using namespace std;

int main() {
    string a,b;
    cin >> a >> b;
    unordered_map<char, int> myMap;
    for (const auto& ch : b) {
        myMap[ch]++;
    }
    for (const auto& ch : a) {
        if (myMap.count(ch)) {
            myMap[ch]--;
            if (myMap[ch] == 0) {
                myMap.erase(ch);
            }
        } else {
            cout << "false" << endl;
            return 0;
        }
    }
    cout << "true" << endl;
    return 0;
}

发表于 2022-07-31 15:03:22 回复(0)
何止hz头像 何止hz
一路看下来似乎没有特别好的解法，这里写了两段AC的Java代码，耗时都比较长。
1： 
import java.util.Scanner;
 
/**
 * @Date: 2020-05-04 18:23
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder t = new StringBuilder().append(sc.next());
        int index;
        for (int i = 0; i < s.length(); i++){
            index = t.indexOf(Character.toString(s.charAt(i)));
            if (index == -1){
                System.out.println(false);
                return;
            }
            t.deleteCharAt(index);
        }
        System.out.println(true);
    }
}
2： 
import java.util.HashMap;
import java.util.Scanner;
 
/**
 * @Date: 2020-05-04 18:48
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        HashMap<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++){
            if (map.get(t.charAt(i)) != null)
                map.put(t.charAt(i), map.get(t.charAt(i))+1);
            else
                map.put(t.charAt(i), 1);
        }
        for (int i = 0; i < s.length(); i++){
            Integer num = map.get(s.charAt(i));
            if (num ==null || num == 0){
                System.out.println(false);
                return;
            }
            map.put(s.charAt(i), num-1);
        }
        System.out.println(true);
    }
}

发表于 2020-05-04 19:02:11 回复(0)
C/C++
旷视内推君头像 旷视内推君 
#include <string>
(765)#include <iostream>
#include <map>
using namespace std;
int main(){
    string s1,s2;
    cin>>s1>>s2;
    map<char,int> mp;
    for (auto s:s2)
        mp[s]++;
    for(auto s:s1){
        if (mp[s]--<=0){
            cout<<"false";
            return 0;
        }
       
    }
    cout<<"true";
}

发表于 2020-04-21 10:49:44 回复(0)
夏花爱秋叶头像 夏花爱秋叶 
// 思路很简单，关键在于，不要多次使用indexOf,那么每次都是n的时间复杂度
// 所以会通过率很低，解决办法就是使用字典存储来代替长长的字符串，这样就可以不去使用indexOf
var line=readline().split(' ')
var small=line[0];
var big=line[1];
// 判断长度
if(small.length>big.length){
    var tem=small;
    small=big;
    big=tem;
}
big=big.split('')
var flag=true;
// 如果每次都使用indexOf,那么会搜索多次big数组，时间复杂度就很大
// 所以最好把big设置为字典
var mymap={}
for(var j=0;j<big.length;j++){
    if(mymap[big[j]]){
        mymap[big[j]]++
    }else{
        mymap[big[j]]=1;
    }
}
for(var i=0;i<small.length;i++){
    if(mymap[small[i]]>0){
        mymap[small[i]]--;
    }else{
        console.log("false")
        flag=false
        break;
    }
}
if(flag){
    console.log("true")
}

发表于 2020-04-06 23:23:42 回复(0)
lhl_CQ头像 lhl_CQ
在较长字符串中删除较短字符串中出现过的字符 
str1,str2 = input().split()
flag = 0
for k in str1:
    if k in str2:
        str2=str2.replace(k,'',1)
    else:
        flag = 1
        break
print('false' if flag==1 else 'true')



发表于 2020-03-20 09:46:10 回复(0)
GreenLeaves🍀头像 GreenLeaves🍀 
import java.util.*;

public class Main{
    
    public static void main(String args[]){
        
        Scanner sc = new Scanner(System.in);
        String str1 = sc.next();
        String str2 = sc.next();
        sc.close();
        System.out.println(canconstruct(str1,str2));
    }
    
    public static boolean canconstruct(String str1, String str2){
        for(int i=0;i<str1.length();i++){
            char c = str1.charAt(i);
            if( str2.indexOf(c) == -1){
                return false;
            }else{
                
            }
        }
        return true;
    }
}
为何测试不通过？
用测试不通过的用例在本地测试却是正确的??
发表于 2020-02-24 19:03:40 回复(2)
牛客282965463头像 牛客282965463 
#include <iostream>
#include <string>

using namespace std;

int main()
{
    const int SIZE = 26;
    //空间换时间，算法复杂度O(m+n+k),空间复杂度O(2*K)
    int arr1[SIZE] = {0};
    int arr2[SIZE] = {0};
    string s1;
    string s2;
    cin >> s1;
    cin >> s2;
    for(char c:s1)
        arr1[c-'a'] += 1;
    for(char c:s2)
        arr2[c-'a'] += 1;
    for(int i = 0; i < SIZE; ++i)
    {
        if(arr1[i] > arr2[i])
        {
            cout << "false" << endl;
            return 0;
        }
    }
    cout << "true" << endl;
    return 0;
}

发表于 2019-11-20 11:00:51 回复(0)
C/C++
hello古斯卡头像 hello古斯卡 
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        String a, b;
        int arr[] = new int[128];
        Scanner cin = new Scanner(System.in);
        a = cin.next();
        b = cin.next();

        for (int i = 0; i < a.length(); i++) {
            arr[a.charAt(i)]++;
        }
        for (int i = 0; i < b.length(); i++) {
            arr[b.charAt(i)]--;
        }
        boolean flag = true;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > 0) {
                flag = false;
                break;
            }
        }

        System.out.println(flag);

    }
}

发表于 2019-10-04 22:05:50 回复(0)
提交观点

问题信息

iOS工程师 动态规划 小米集团 字符串 2019 查找
来自：小米2019秋招iOS...
上传者：小小
难度：
26条回答 10081浏览

热门推荐

通过挑战的用户

查看代码

相关试题

构建短字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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