[LeetCode] 916. Word Subsets

https://leetcode.com/problems/word-subsets/description/

leetcode - Word Substts

문제 유형: 문자열 처리, 집합

문제 난이도: 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.

 

두 개의 문자열 배열 words1과 words2를 받는다.

개수까지 고려해서 문자열 b의 모든 글자가 a에 포함될 때 부분집합이라 한다.

words1의 문자열이 words2의 모든 문자열을 부분집합으로 가진다면, a는 범용적인 문자열이다.

words1에서의 범용적인 문자열들을 찾아 반환하시오. 순서는 상관 없습니다.

 

풀이

우선, words2의 단어들에 대한 모든 글자 빈도에 대한 합집합을 만든다.

그 뒤, words1의 단어들을 읽으면서 모든 글자빈도 합집합을 포함하는지 확인해주면 된다.

 

코드

C++

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        vector<int> freq(26, 0);
        for(const auto &word : words2) {
            vector<int> temp(26, 0);
            for(const auto &ch : word) {
                temp[ch - 'a']++;
            }
            for(int i = 0; i < 26; ++i) {
                freq[i] = max(freq[i], temp[i]);
            }
        }

        vector<string> ans;
        for(const auto &word : words1) {
            vector<int> temp(26, 0);          
            bool flag = true;
            for(const auto &ch : word) {
                temp[ch-'a']++;
            }
            for(int i = 0; i < 26; ++i) {
                if(temp[i] - freq[i] < 0) {
                    flag = false;
                    break;
                }
            }
            if(flag) ans.push_back(word);
        }

        return ans;
    }
};