蓝桥杯备赛-基础训练（三）哈希表 day16

今天一更

赎金信

题意：

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

思路：

这里需要注意的主要就是：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。所以最好使用map，要记录一个字母出现的次数。

类似之前的有效的字母异位词，我们最后主要是判断是否都为0

1、定义dict_zazhi = dict()

2、定义dict_shujin = dict()

3、把杂志上的字都录入dict_shujin当中

4、赎金信上的字母遇到了就-=1 

5、最后循环看是否每个字符都大于0

但是后来发现，其实这里用数组就可以了，因为map还需要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！

具体的思路和上面几乎是一样的

# 赎金信
zazhi = [0]*26
x = input("请你输入杂志的内容，一个字母一个字母的输入，并且只能输入小写字母，以空格为间隔：").split()
y = input("请你输入赎金信的内容，一个字母一个字母的输入，并且只能输入小写字母，以空格为间隔：").split()
print(x)
print(y)

for i in x:
    zazhi[ord(i)-ord('a')]+=1
print(zazhi)
for i in y:
    zazhi[ord(i)-ord('a')]-=1
print(zazhi)

judge = 0
for i in range(26):
    if zazhi[i]<0:
        judge = 1

if judge==0:
    print("可以组成赎金信")
else:
    print("不可以组成赎金信")

# 赎金信内容
# i l i k e a p p l e i t h i n k t h i s t h i n g s i s v e r y g o o d
# 杂志内容
# t o d a y i a m v e r y h a p p y w h f f f g g g g a t a r e y o u t h i n k i l i k e s o m e m i l k s s s s i i i d d d n n n