哈希表第7/9题--赎金信

题目描述：

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

leetcode链接：LeetCode383

思路分析：

要注意这一句：magazine 中的每个字符只能在 ransomNote 中使用一次， 即杂志里面的字母不能重复使用；

提示里面这一句也比较重要：ransomNote 和 magazine 由小写英文字母组成；

本题可以使用多种解法来进行求解，首先我们来看最简单的方法：使用count来进行。遍历赎金信中的的每个字母，如果这个字母在杂志中出现并且赎金信中这个字母出现的次数小于等于杂志中出现的次数，则继续循环下一个字母，否则返回false。全部字母循环结束后返回True。

总结下来其实就两点：1.赎金信中每个字母必须都要在杂志中出现；2.赎金信中每个字母出现的次数要小于等于在杂志中出现的次数。

如果使用数组来解题的话，首先定义两个数组来作为哈希表，利用ASCII码值于a的ASCII值的差值来作为索引，遍历每个字母，当前字母减去ord('a')作为索引，每出现一次就加一次1，得到赎金信和杂志字母分布的两个hash表。迭代判断是否在所有的26个字母的位置中，赎金信的hash值小于等于杂志的hash值。如果不全为True，则all函数返回False。

代码分析：

# 最简单的方法，使用count来计算
class Solution:
     def canConstruct(self, ransomNote: str, magazine: str) -> bool:
         # 循环遍历赎金信中的每个字母
         for char in ransomNote:
         # 如果字母在杂志中出现，并且赎金信中这个字母出现的次数《=杂志中这个字母出现的次数，则跳过
             if char in magazine and ransomNote.count(char) <= magazine.count(char):
                 continue
             # 否则返回False
             else:
                 return False
         return True

# 使用数组来解题，由于字母总数最多只有26个，所以用数组做hash表比较实用
class Solution:
    # 预定义两个字符串类型，返回布尔值
    def canConstruct(self, ransomNote:str, magazine:str) -> bool:
        # 定义两个长度为26，值为0的列表
        ransom_count = [0] * 26
        magazine_count = [0] * 26
        # 循环获取赎金信中的每个字母
        for c in ransomNote:
            # 在出现的字母的位置记录该字母出现的次数
            ransom_count[ord(c)- ord('a')] += 1
        for c in magazine:
            # 同上
            magazine_count[ord(c) - ord('a')] += 1
        # all函数是当元组中全不为0，False或者none时返回True
        return all(ransom_count[i] <= magazine_count[i] for i in range(26))