一、题目描述

电视剧《分界线》里面有一个片段，男主为了向警察透露案件细节，且不暴露自己，于是将报刊上的字剪切下来，剪拼成匿名信。现在有一名举报人，希望借鉴这种手段，使用英文报刊完成举报操作。

但为了增加文章的混淆度，只需满足每个单词中字母数量一致即可，不关注每个字母的顺序解释:单词on允许通过单词’no’进行替代报纸代表newspaper，匿名信代表anonymousLetter,求报纸内容是否可以拼成匿名信。

二、输入描述

第一行输入newspaper内容，包括1-N个字符串，用空格分开
第二行输入anonymousLetter内容，包括1-N个字符串，用空格分开

1. newspaper和anonymousLetter的字符串由小写英文字母组成且每个字母只能使用一次；
2. newspaper内容中的每个字符串字母顺序可以任意调整,但必须保证字符串的完整性(每个字符串不能有多余字母)；
3. 1<N<100 , 1<= newspaper.length, anonymousLetter.length <= 104；

三、输出描述

如果报纸可以拼成匿名信返回ture，否则返回false。

四、解题思路

1. 读取输入的报纸内容和匿名信内容。
2. 将报纸内容和匿名信内容分别以空格为分隔符拆分成字符串数组。
3. 创建一个HashSet，用于存储报纸内容中每个字符串按字母排序后的值。
4. 遍历报纸内容数组：
   • 对于每个字符串，将其转换为字符数组，并按字母顺序进行排序。
   • 将排序后的字符数组转换为字符串，并添加到HashSet中。
5. 创建一个布尔变量flag，并将其初始化为true。
6. 遍历匿名信内容数组：
   • 对于每个字符串，将其转换为字符数组，并按字母顺序进行排序。
   • 将排序后的字符数组转换为字符串。
   • 如果HashSet中不包含该字符串，则将flag设为false，并跳出循环。
7. 根据flag的值，输出"true"或"false"表示报纸是否可以拼成匿名信。

该算法的时间复杂度为O(N+M)，其中N是报纸内容的长度，M是匿名信内容的长度。因为需要遍历两个字符串数组，对每个字符串进行排序，并将排序后的字符串存储到HashSet中。最终的空间复杂度为O(N)，取决于HashSet的存储空间。

五、Python算法源码

import sysdef test():# 读取第一行的narr1=[]for i in range(2):# 读取每一行line = sys.stdin.readline().strip()# 把每一行的数字分隔后转化成int列表arr3=[]arr4=[]arr2 = list(map(str, line.split()))for j in range(len(arr2)):for k in arr2[j]:arr3.append(k)arr3.sort()arr4.append(arr3)arr3=[]arr1.append(arr4)for i in range(len(arr1[1])):if arr1[1][i] in arr1[0]:arr1[0].remove(arr1[1][i])else:return('false')return('true')
print (test())

六、效果展示

1、输入

ac df
adf

2、输出

false

🏆下一篇：华为OD机试真题 Python 实现【相对开音节】【2022Q4 100分】，附详细解题思路

🏆本文收录于，华为OD机试（Python）真题（A卷+B卷）

每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。