构建短字符串

[编程题]构建短字符串

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

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

输入描述:

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

输出描述:

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

示例1

输入

a b

输出

false

示例2

输入

fj jfiejfiejfie

输出

true

算法知识视频讲解

Python3

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)