【Python3】【力扣题】383.赎金信

【力扣题】题目描述：

题解：

两个字符串ransomNote和magazine，ransomNote中每个字母都在magazine中一一对应（顺序可以不同）。

即分别统计两个字符串中每个字母出现的次数，ransomNote中每个字母的个数小于等于magazine中该字母对应的个数。

【Python3】代码：

1、解题思路：使用collections.Counter()分别统计两字符串的字母及出现次数，比较相同字母的个数。

（1-1）若某字母在ransomNote中的个数大于在magazine中的个数，则有元素在magazine字符串中不存在。

知识点：len(...)：获取序列（字符串、列表等）的长度。

              collections.Counter(...)：字典子类，计数器，统计元素和元素出现的次数。

              字典.items()：返回可迭代的字典的所有键值对，键值对是元组形式 (键, 值)。

              字典[键]：获取字典中键对应的值。也可给键赋值或修改值：字典[键]=值。

class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: from collections import Counter if len(ransomNote) > len(magazine): return False a, b = Counter(ransomNote), Counter(magazine) for k,v in a.items(): if a[k] > b[k]: return False return True

（1-2）两个计数器相减，即相同的键对应的值相减，若相减后仍有元素的值大于0，则有元素在magazine字符串中不存在。

知识点：collections.Counter(可迭代对象1) - collections.Counter(可迭代对象2)：两个可迭代对象中相同元素的值相减，只返回结果值大于0的元素。

class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: from collections import Counter if len(ransomNote) > len(magazine): return False return not Counter(ransomNote) - Counter(magazine)

注解：

2、解题思路：用一个字典记录每个字母的个数。

（2-1）字符串ransomNote中统计每个字母的个数，字符串magazine将字母对应的个数从字典中减去。若最终字典中有字母的值大于0，则有元素在magazine字符串中不存在。

知识点：collections.defaultdict(...)：字典子类，若字典中某键不存在，则调用工厂函数返回默认值。

              字典.values()：返回可迭代的字典的所有值。

class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: from collections import defaultdict if len(ransomNote) > len(magazine): return False d = defaultdict(int) for x in ransomNote: d[x] += 1 for y in magazine: d[y] -= 1 for val in d.values(): if val > 0: return False return True

（2-2）两个字符串反过来统计，字符串magazine中统计每个字母的个数，字符串ransomNote将字母对应的个数从字典中减去，若减去后该字母的值小于0，则有元素在magazine字符串中不存在。

class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: from collections import defaultdict if len(ransomNote) > len(magazine): return False d = defaultdict(int) for y in magazine: d[y] += 1 for x in ransomNote: d[x] -= 1 if d[x] < 0: return False return True

3、解题思路：用一个列表记录每个字母的个数。以字母距离“a”的间隔作为下标。字符串ransomNote中统计每个字母总个数，字符串magazine将字母对应的个数从列表中减去。若结果中有元素大于0，则有元素在magazine字符串中不存在。

（3-1）知识点：[0]*26：即长度为26的元素都是0的列表，[0,0,...0,0]。

             ord(...)：获取字符的ascii值或unicode值。

             列表[下标]：获取列表中下标对应的元素。也可修改下标对应的元素值：列表[下标]=值。

class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: if len(ransomNote) > len(magazine): return False alist = [0] * 26 for x in ransomNote: alist[ord(x) - ord("a")] += 1 for y in magazine: alist[ord(y) - ord("a")] -= 1 for val in alist: if val > 0: return False return True

（3-2）知识点：itertools.chain(可迭代对象1, 可迭代对象2,...)：返回一个迭代器，包含多个可迭代对象的所有元素。

             enumerate(...)：返回可迭代的所有元素下标和元素，元组形式 (下标, 元素)。

class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: from itertools import chain n = len(ransomNote) if n > len(magazine): return False alist = [0] * 26 for i,x in enumerate(chain(ransomNote,magazine)): if i < n: alist[ord(x)-ord("a")] += 1 else: alist[ord(x)-ord("a")] -= 1 for val in alist: if val > 0: return False return True

（3-3）知识点：itertools.zip_longest(可迭代对象1, 可迭代对象2, fillvalue=None)：返回一个迭代器，将两个可迭代对象的元素按对应位置一一组成元组。所有元素遍历完，若其中一个可迭代对象没有元素了，可用fillvalue参数指定默认值来填充空缺，若没有指定fillvalue，则用None填充空缺。

class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: from itertools import zip_longest if len(ransomNote) > len(magazine): return False alist = [0] * 26 for x,y in zip_longest(ransomNote,magazine,fillvalue=0): if x != 0: alist[ord(x)-ord("a")] += 1 if y != 0: alist[ord(y)-ord("a")] -= 1 for val in alist: if val > 0: return False return True

4、解题思路：将字符串ransomNote中字母去重，再遍历元素，比对字母在两个字符串中出现的次数，若所有字母在ransomNote中的个数都小于magazine中的个数，则返回True。

知识点：set(...)：转为集合，集合中的元素不重复。

              序列.count(...)：统计元素在序列（字符串，列表等）中出现的次数。

              all(...)：判断可迭代对象（元组，列表）中的所有元素是否都为True。

class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: if len(ransomNote) > len(magazine): return False return all(ransomNote.count(x) <= magazine.count(x) for x in set(ransomNote))