Description

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

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 = ["lc","eo"]

Output: ["leetcode"]

Example 3:

Input: words1 = ["acaac","cccbb","aacbb","caacc","bcbbb"], words2 = ["c","cc","b"]

Output: ["cccbb"]

---

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.

---

내 풀이

모든 words1 에 대해 매번 words2 의 글자를 하나씩 지워가며 universal(모두 포괄하는) words1 요소를 골라내는 방법을 생각했다.
사람이 일일이 하나씩 확인하는 방식을 채택해서 구현한 코드이다.

class Solution:
    def wordSubsets(self, words1, words2):
        result = []
        def findSubsets(word, letters):
            word_rep = word
            for letter in list(letters):
                try:
                    word_rep.index(letter)
                    word_rep = word_rep.replace(letter, '', 1)
                except:
                    return False
            return True

        for word in words1:
            check = 0
            for letter in words2:
                if findSubsets(word, letter) : check += 1
            if check == len(words2): 
                result.append(word)
        return result

문제를 해결하는 것은 가능하나, O($N_1$×$N_2$×$M$×$L$) 수준의 시간복잡도로 인해 시간 제한을 넘겨버리는 문제가 발생한다.

• $N_1$ : words1의 길이
• $N_2$ : words2의 길이
• $M$: words2의 각 문자열(letters)의 평균 길이
• $L$: words1의 각 문자열(word)의 평균 길이

가능한 풀이

단어의 부분집합이라는 관점보다는, example 3의 예시를 통해 얻을 수 있는 관점이 문제 풀이의 핵심이다.
만약 'cc' 가 포함된 단어라면, 'c' 하나가 포함되는 경우는 자연스럽게 통과할 수 있다. 다르게 풀어서 말하면, 검사할 단어들의 알파벳 최대 개수를 정리해서 검사를 진행할 수 있다.
따라서 words2 의 각 단어가 가지는 알파벳의 최대 개수를 기록하고, words1 의 단어의 알파벳 개수와 비교하여 결과를 도출할 수 있다.

class Solution:
    def wordSubsets(self, words1: List[str], words2: List[str]) -> List[str]:
        maxCharFreq = [0] * 26
        tempCharFreq = [0] * 26

        for word in words2:
            for ch in word:
                tempCharFreq[ord(ch)-ord('a')] += 1
            for i in range(26):
                maxCharFreq[i] = max(maxCharFreq[i], tempCharFreq[i])
            tempCharFreq = [0] * 26
        
        universalWords = []

        for word in words1:
            for ch in word:
                tempCharFreq[ord(ch)-ord('a')] += 1
            isUniversal = True
            for i in range(26):
                if maxCharFreq[i] > tempCharFreq[i]:
                    isUniversal = False
                    break
            if isUniversal:
                universalWords.append(word)
            tempCharFreq = [0] * 26
        return universalWords