[LeetCode] 916. Word Subsets (Python)

 

난이도: Medium

 

문제 설명

---

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 words2, b 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"]

 

제한 사항

---

• 1 <= words1.length, words2.length <= 10^4
• 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.

 

Solution(솔루션)

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        answer = []
        count_words2 = Counter(words2[0])

        for i in range(1, len(words2)):
            count_words2 |= Counter(words2[i])

        for word1 in words1:
            c1 = Counter(word1)
            check = True
            for key in count_words2:
                if c1[key] < count_words2[key]:
                    check = False
                    break
            if check:
                answer.append(word1)
                           
        return answer

 

처음에는 모든 words1의 단어들에 대해 각각 모든 words2의 요소들을 비교하여 정답을 구했다.

 

하지만 이는 TLE가 발생했다.

 

그래서 생각한 것이 words2에 요소를 한번에 저장해 놓고 이를 words1의 단어와 비교하면 되지 않을까 였다.

 

예를 들어, words2 = ["ab", "bc"] 라고 한다면, 최종적으로 {'a':1, 'b':1, 'c':1} 를 만족하는 word1을 찾으면 될 것 같았다.

 

따라서, Counter의 or 연산을 통해 위 작업을 수행하였고, words1의 단어들을 이와 비교하여 조건을 만족하면 answer에 이를 append하였다.

 

마지막에는 answer를 return하여 정답을 맞출 수 있었다.

---

문제: 916. Word Subsets

 

깃허브: github

algorithm_practice/LeetCode/952-word-subsets at main · laewonJeong/algorithm_practice