构建短字符串

[编程题]构建短字符串

热度指数：4381 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定任意一个较短的子串，和另一个较长的字符串，判断短的字符串是否能够由长字符串中的字符构建出来，且长串中的每个字符只能用一次。

输入描述:

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

输出描述:

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

示例1

输入

a b

输出

false

示例2

输入

fj jfiejfiejfie

输出

true

算法知识视频讲解

Python

贾志统

S, T = input().split()
T_dic = dict()
for ch in T:
    T_dic[ch] = T_dic.setdefault(ch, 0) + 1
flag = 1
for ch in S:
    if ch not in T_dic:
        flag = 0
        break
    elif T_dic[ch] <= 0:
        flag = 0
        break
    else:
        T_dic[ch] -= 1
if flag == 0:
    print("false")
else:
    print("true")

发表于 2019-09-06 11:50:40 回复(0)

Python

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)