0916._Word_Subsets.md

916. Word Subsets

难度: Medium

刷题内容

原题连接

• https://leetcode.com/contest/weekly-contest-104/problems/word-subsets/

内容描述

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 <= 10000
1 <= A[i].length, B[i].length <= 10
A[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].

解题方案

思路 1 - 时间复杂度: O(max(mala, mblb))- 空间复杂度: O(1)****

假设A的长度为na，其中最长的一个单词长度为la B的长度为nb，其中最长的一个单词长度为lb

那么时间复杂度为O(max(mala, mblb))，由于字符总共就26个，所以空间复杂度可以看作O(1)

先求出B中所有字符在所有单词中出现的最大次数，用lookup记录，然后如果A中的某一个单词满足lookup里面所有的key都有，且对应数量都大于等于lookup中的， 那么该单词满足条件，append到最终结果中

class Solution(object):
    def wordSubsets(self, A, B):
        """
        :type A: List[str]
        :type B: List[str]
        :rtype: List[str]
        """
        if not B or len(B) == 0:
            return A
        lookup = collections.Counter(B[0])
        for word in B[1:]:
            tmp = collections.Counter(word)
            for key in tmp.keys():
                if key not in lookup:
                    lookup[key] = tmp[key]
                else:
                    lookup[key] = max(lookup[key], tmp[key])
        def uni(tmp_a, tmp_b):
            if len(tmp_a.keys()) < len(tmp_b.keys()):
                return False
            for key in tmp_b.keys():
                if key not in tmp_a:
                    return False
                else:
                    if tmp_a[key] < tmp_b[key]:
                        return False
            return True
        res = []
        for word in A:
            if uni(collections.Counter(word), lookup):
                res.append(word)
        return res