[leetcode] 916. Word Subsets

[leetcode] 916. Word Subsets

Description

We are 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”.

Now say 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 <= A.length, B.length <= 100001 <= A[i].length, B[i].length <= 10A[i] and B[i] consist only of lowercase letters.All words in A[i] are unique: there isn’t i != j with A[i] == A[j].

分析

题目的意思是：给定一个字符串数组A，判断b中所有的字符是否是a的子集，我一开始用字典做了一下，发现b中的字符是字符串，然后没有ac。我参考了一下答案的思路，count统计的是word的词频，bmax统计的是b中每个字符串最大词频。如果A能够满足b对于字符的最大词频，则满足条件，如果知道这个，剩下的就是遍历A看A中的字符串能够满足条件了哈。

代码

class Solution: def count(self,word): ans=[0]*26 for ch in word: ans[ord(ch)-ord('a')]+=1 return ans def wordSubsets(self, A: List[str], B: List[str]) -> List[str]: bmax=[0]*26 for b in B: for i,c in enumerate(self.count(b)): bmax[i]=max(bmax[i],c) res=[] for a in A: flag=True for x,y in zip(self.count(a),bmax): if(x

参考文献

​​[LeetCode] solution​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。