엔지니어 게시판
LeetCode 솔루션 분류

[7/30] 916. Word Subsets

컨텐츠 정보

본문

Medium
2162180Add to ListShare

You are given two string arrays words1 and words2.

A string b is a subset of string 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".

A string a from words1 is universal if for every string b in words2b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

 

Example 1:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
Output: ["apple","google","leetcode"]

 

Constraints:

  • 1 <= words1.length, words2.length <= 104
  • 1 <= words1[i].length, words2[i].length <= 10
  • words1[i] and words2[i] consist only of lowercase English letters.
  • All the strings of words1 are unique.
Accepted
88,270
Submissions
164,125
태그

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
Runtime: 1334 ms, faster than 46.34% of Python3 online submissions for Word Subsets.
Memory Usage: 18.9 MB, less than 23.33% of Python3 online submissions for Word Subsets.
import collections
class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        word2_union = collections.defaultdict(int)
        for word in words2:
            temp_counter = collections.Counter(word)
            for key in temp_counter:
                word2_union[key] = max(word2_union[key], temp_counter[key])
        
        res = []
        
        for word in words1:
            temp_counter = collections.Counter(word)
            res.append(word)
            for key in word2_union:
                if key not in temp_counter or temp_counter[key] < word2_union[key]: 
                    res.pop(); break;
        
        return res
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0