哈希表（计数）— 赎金信

文章目录一、[题目](https://leetcode.cn/problems/ransom-note/description/?envTypestudy-plan-v2envIdtop-interview-150)二、My thinking三、哈希表3.1 思路3.2 算法步骤3.3 代码实现3.4 时间和空间复杂度四、总结一、题目给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以返回 true 否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。为什么题目叫赎金信绑匪要写一封勒索信ransom note为了不让警方通过笔迹追踪到自己他决定从杂志magazine上剪下一个个字母拼成这封信。示例1 输入ransomNotea,magazineb输出false 示例2 输入ransomNoteaa,magazineab输出false 示例3 输入ransomNoteaa,magazineaab输出true二、My thinkingreturn None三、哈希表3.1 思路检查 ransomNote 中每个字符的出现次数是否都 ≤ magazine 中的出现次数。可以用哈希表统计每个字符串中每个字符的数量。3.2 算法步骤初始用一个哈希表表示magazine里每个字符的数量得到一个字典遍历遍历ransomNote中的字符拿从ransomNote遍历得到的字符去字典里哈希判断如果哈希不到ransomNote遍历的这个字符不在magazine里返回False要是能哈希到说明ransomNote遍历的这个字符在magazine里将字典里这个字符的数值减1因为只能使用一次3.3 代码实现fromcollectionsimportCounterclassSolution:defcanConstruct(self,ransomNote:str,magazine:str)-bool:countCounter(magazine)forchinransomNote:ifcount[ch]0:returnFalsecount[ch]-1returnTrue更简洁的写法fromcollectionsimportCounterclassSolution:defcanConstruct(self,ransomNote:str,magazine:str)-bool:# Counter 支持加法、减法、交集和并集等算术运算。returnnot(Counter(ransomNote)-Counter(magazine))3.4 时间和空间复杂度时间复杂度使用Counter对magazine遍历计数后面的for循环又遍历了一次时间复杂度与两个字符串的长度有关时间复杂度为O(n)空间复杂度用count存储magazine字符串的计数字符集固定为26与字符串规模无关所以空间复杂度为O(1)四、总结Counter是Python内置模块collections中的一个计数器工具可以方便快捷地计数。Counter 支持加法、减法、交集和并集等算术运算。看到「计数」「次数」「够不够」就想到哈希表。