首页 > 试题广场 > 构建短字符串
[编程题]构建短字符串
给定任意一个较短的子串,和另一个较长的字符串,判断短的字符串是否能够由长字符串中的字符构建出来,且长串中的每个字符只能用一次。

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


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

输入

a b

输出

false
示例2

输入

fj jfiejfiejfie

输出

true
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 回复(0)
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)
""""
一种借助字典的思路,时间复杂度较低
"""
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)
#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)
#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)
s, t = input().strip().split()
count = 0
for i in set(s):
    if s.count(i) <= t.count(i):
        count += 1
    else:
        print("false")
        break
if count == len(set(s)):
    print("true")  

发表于 2019-08-04 19:29:12 回复(0)
[short, long] = input().split()
def helper(short, long):
    dic = {}
    for i in long:
        dic[i] = dic.get(i, 0)+1

    for j in short:
        if j not in dic or dic[j] <= 0:
            return 'false'
        else:
            dic[j] -= 1

    return 'true'

print(helper(short, long))

发表于 2019-07-26 09:27:10 回复(0)
a,b = input().split(' ')
from collections import defaultdict
a1 = defaultdict(int)
b1 = defaultdict(int)
for i in a:
    a1[i]+=1
for i in b:
    b1[i]+=1
for i in a:
    if a1[i]>b1[i]:
        break
print('false' if a1[i]>b1[i] else 'true')

发表于 2019-07-11 16:36:39 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main()
{
    string S,T;   //短字符串S,长字符串T
    while(cin >> S >> T)
    {
        map<char,int> m;   //map用来存放字符串T中出现过的字符及其出现次数
        bool flag = true;   //用来判断能不能构建短字符串
        for(auto it : T)
        {
            m[it]++;
        }
        for(auto it : S)
        {
            if(m[it])
            {
                m[it]--;
            }
            else
            {
                flag = false;
            }
        }
        printf("%s\n", flag ? "true" : "false");  //不想写if-else了,直接来?:
    }
    return 0;
}

发表于 2019-06-29 11:52:17 回复(0)