题目地址: https://leetcode.com/problems/word-subsets/description/
题目描述：
Weare given two arrays A and B of words. Each word is a string of lowercase letters.
Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity. For example, "wrr" is a subset of "warrior", but is not a subset of "world".
Nowsay a word a from A is universal if for every b in B, b is a subset of a.
Return a list of all universal words in A. You can return the words in any order.
Example 1:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]
Example 2:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
Output: ["apple","google","leetcode"]
Example 3:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
Output: ["facebook","google"]
Example 4:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]
Example 5:
Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
Output: ["facebook","leetcode"]
Note:
1、 1<=A.length,B.length<=10000；
2、 1<=A[i].length,B[i].length<=10；
3、 A[i]andB[i]consistonlyoflowercaseletters.；
4、 AllwordsinA[i]areunique:thereisn'ti!=jwithA[i]==A[j].；
题目大意
如果B中的每一个元素中的每个字符都能在A中的某个字符串中找到，那么这个是个符合要求的字符串。求A中所有满足要求的字符串。
解题方法
如果按照题目要求的意思去直接做，那么要遍历B的每个元素的每个字符与A对应，这个时间复杂度肯定过不了OJ。所以，采用了一个很巧妙的方法，把B当做一个限制条件，直接求解这个限制条件。
对B的每个元素遍历，然后统计每个元素中每个字符串出现的次数，更新整体限制条件为每个元素在字符串中出现的次数的最大值。
统计结束之后，对A遍历的时候，只要看A是否满足这个限制条件就行了，所以挺快的。
时间复杂度是O(N)，空间复杂度是O(N)。
class Solution(object):
def wordSubsets(self, A, B):
"""
:type A: List[str]
:type B: List[str]
:rtype: List[str]
"""
B = set(B)
res = []
count = collections.defaultdict(int)
for b in B:
cb = collections.Counter(b)
for c, v in cb.items():
count[c] = max(count[c], v)
res = []
for a in A:
ca = collections.Counter(a)
isSuccess = True
for c, v in count.items():
if v > ca[c]:
isSuccess = False
break
if isSuccess:
res.append(a)
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
参考资料：
https://leetcode.com/problems/word-subsets/discuss/175854/C++JavaPython-Straight-Forward
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发