916. Word Subsets

https://leetcode.com/problems/word-subsets/description/?envType=daily-question&envId=2025-01-10

 

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

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

 

 

words1을 순회하면서, 각 문자열이 words2의 부분집합으로 만들 수 있는지 검사하는 문제였다.

 

내가 접근한 방식은 다음과 같다.

1. words2를 순회하면서 각 문자의 등장횟수를 모두 더해준다.
2. words1를 순회하면서 각 등장횟수를 저장한다.
3. words2를 저장한 해쉬맵의 키를 돌면서, containsKey 여부와 등장횟수를 체크한다.
4. 만약에 containsKey와 words1의 등장횟수가 많은 경우에만 결과값에 넣어준다.

 

예제는 다 통과했지만, 해당 예제에서 통과하지 못했다.

words1 =["amazon","apple","facebook","google","leetcode"]words2 =["lo","eo"]

Use Testcase
Output["google"]
Expected["google","leetcode"]

 

word2 Map

l: 1, e: 1, o:2

 

word1 Map (Leetcode)

l: 1, e:3, o: 1

 

나의 로직 상으로 word1의 o 등장횟수가 더 적기때문에 leetcode 단어가 결과값에 포함하면 안됐지만, 그 차이때문에 틀렸다. 

 

현재 나의 코드는 

words2 = ["lo", "eo"]일때 모든 문자를 합산하기 때문인데,

l:1, o:1, e:1 처럼 최대 등장횟수를 계산해야한다. 

 

따라서, 2개의 Map을 선언하여 max값에 해당하는 등장횟수만 저장하도록 구현해서 통과했다.

 

정답 코드

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> res = new ArrayList<>();

        int [] maxFreq = new int[26];
        for(String word : words2) {
            int [] freq = new int[26];
            for(char c : word.toCharArray()) {
                freq[c - 'a']++;
            }

            for(int i = 0; i < 26; i++) {
                maxFreq[i] = Math.max(maxFreq[i], freq[i]);
            }
        }

        for(String word : words1) {
            int [] wordFreq = new int[26];
            for(char c : word.toCharArray()) {
                wordFreq[c - 'a']++;
            }

            boolean flag = true;
            for(int i = 0; i < 26; i++) {
                if (wordFreq[i] < maxFreq[i]) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                res.add(word);
            }
        }
        return res;
    }
}

 

 

맵을 사용하는 것보다 배열을 사용하는 것이 시간복잡도 측면에서나 코드 가독성에서나 훨씬 뛰어났다.