难度：★★★☆☆
类型：字符串
方法：统计
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
我们给出两个单词数组 A 和 B。每个单词都是一串小写字母。
现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称单词 b 是单词 a 的子集。 例如，“wrr” 是 “warrior” 的子集，但不是 “world” 的子集。
如果对 B 中的每一个单词 b，b 都是 a 的子集，那么我们称 A 中的单词 a 是通用的。
你可以按任意顺序以列表形式返回 A 中所有的通用单词。
示例 1：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
输出：["facebook","google","leetcode"]
示例 2：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
输出：["apple","google","leetcode"]
示例 3：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
输出：["facebook","google"]
示例 4：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
输出：["google","leetcode"]
示例 5：
输入：A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
输出：["facebook","leetcode"]
提示：
1 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].length <= 10
A[i] 和 B[i] 只由小写字母组成。
A[i] 中所有的单词都是独一无二的，也就是说不存在 i != j 使得 A[i] == A[j]。
解答
分析题目的规则是，如果单词b中各个单词的统计数量不超过单词a的，那么就可以说b是a的子集，无关于字母在单词中的顺序。
这道题看似需要嵌套循环，但是当我们把思路理清楚就会发现，对于字符串列表B，其实可以将其中的所有单词做一个合并，我们只需要统计一下各个单词中每个字母出现次数的最大值就好了，这样，整个的单词列表就可以仅仅看做单词b，进而用它去判断单词b是否为A列表中各个单词的子集，因为只要b是单词a的子集，那么B列表中的每个单词都是a的子集。
这也就是官网的解决方案，用一个长度为26的整数列表记录单词中各字符出现次数。
class Solution(object):
def wordSubsets(self, A, B):
def count(word):
ans = [0] * 26
for letter in word:
ans[ord(letter) - ord('a')] += 1
return ans
bmax = [0] * 26
for b in B:
for i, c in enumerate(count(b)):
bmax[i] = max(bmax[i], c)
ans = []
for a in A:
if all(x >= y for x, y in zip(count(a), bmax)):
ans.append(a)
return ans
我们做一个代码上的合并简化，当然速度略有下降：
class Solution(object):
def wordSubsets(self, A, B):
def count(word):
ans = [0] * 26
for letter in word:
ans[ord(letter) - ord('a')] += 1
return ans
bmax = [max(count(b)[i] for b in B) for i in range(26)]
return filter(lambda word: all(ca >= cb for ca, cb in zip(count(word), bmax)), A)
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
网友评论