916. Word Subsets

문제 링크


내 코드

첫 아이디어 TLE 나서 GPT 참고.

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        vector<string> answer;

        int n = words1.size(), m = words2.size();
        vector words1Dat(n, vector(26, 0));
        vector words2Dat(m, vector(26, 0));

        for(int i{};i<m;++i) { // words2
            for(int j{};j<words2[i].size();++j) {
                words2Dat[i][words2[i][j] - 'a']++;
            }
        }
        
        for(int i{};i<n;++i) { // words1
            for(int j{};j<words1[i].size();++j) {
                words1Dat[i][words1[i][j] - 'a']++;
            }

            bool chk{};
            for(int j{};j<m;++j) {
                for(int k{};k<26;++k) {
                    if(words1Dat[i][k] < words2Dat[j][k]) {
                        chk = true;
                        break;
                    }
                }
                if(chk) break;
            }
            if(!chk) answer.push_back(words1[i]);
        }
        return answer;
    }

    bool checkSubStr(string& s1, string& s2) {
        if(s1.length() < s2.length()) return false;
        
        int j{};
        for(int i{};i<s1.length();++i) {
            if(s1[i] == s2[j]) ++j;
            if(j == s2.size()) break;
        }

        if(j==s2.size()) return true;
        return false;
    }
};

GPT (o3-mini-high)

이 문제는 두 개의 문자열 배열 AA와 BB가 주어질 때, AA의 각 문자열이 BB에 있는 모든 문자열의 서브셋을 포함하는지를 판단하여 조건을 만족하는 AA의 문자열들을 반환하는 문제입니다.

이 문제의 핵심은 BB의 모든 문자열의 요구사항을 하나의 “최대 빈도 테이블”로 병합하여 AA의 문자열과 비교하는 것입니다.

코드 설명

  1. 최대 빈도 테이블 생성:

    • BB의 각 문자열에 대해 각 문자별 빈도를 계산하고, 동일 문자의 최대 빈도를 추적합니다.
    • 이를 통해 BB의 모든 문자열을 만족하기 위해 AA의 문자열이 가져야 하는 최소 조건을 계산합니다.

  2. 유니버설 단어 판단:

    • A A의 각 단어에 대해 bmaxcountb_max_count를 만족하는지를 확인합니다.
    • 특정 문자가 bmaxcountb_max_count에 요구되는 빈도보다 적다면 해당 단어는 유니버설 단어가 아닙니다.

  3. 결과 필터링:

    • A A의 모든 단어를 순회하며 유니버설 조건을 만족하는 단어들만 결과에 추가합니다.

시간 복잡도

  • B B 처리: O(∣B∣ timesLB)O(|B| \ times L_B), 여기서 LB L_B는 B B 내의 문자열의 평균 길이.
  • A A 처리: O(∣A∣ timesLA)O(|A| \ times L_A), 여기서 LA L_A는 A A 내의 문자열의 평균 길이.
  • 최종적으로 O(∣A∣ timesLA+∣B∣ timesLB)O(|A| \ times L_A + |B| \ times L_B)입니다.

346ms, 167.5MB

class Solution {
public:
    vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
        // Function to compute character frequency map
        auto getCharFrequency = [](const string& word) {
            unordered_map<char, int> freq;
            for (char c : word) {
                freq[c]++;
            }
            return freq;
        };

        // Create the maximum frequency map for all words in B
        unordered_map<char, int> bMaxCount;
        for (const string& b : B) {
            unordered_map<char, int> bCount = getCharFrequency(b);
            for (const auto& [ch, count] : bCount) {
                bMaxCount[ch] = max(bMaxCount[ch], count);
            }
        }

        // Check if a word is universal
        auto isUniversal = [&](const string& word) {
            unordered_map<char, int> wordCount = getCharFrequency(word);
            for (const auto& [ch, count] : bMaxCount) {
                if (wordCount[ch] < count) {
                    return false;
                }
            }
            return true;
        };

        // Filter words in A
        vector<string> result;
        for (const string& word : A) {
            if (isUniversal(word)) {
                result.push_back(word);
            }
        }

        return result;
    }
};

Solution

Approach: Reduce to Single Word in B

  • 67ms, 106.80MB
  • Complexity
    • Let A\mathcal{A} and B\mathcal{B} represent the total information in words1 and words2, respectively.
    • Time Complexity: O(A+B)O(\mathcal{A} + \mathcal{B})
    • Space Complexity: O(1) or O(A.length)O(1) \ or \ O(\mathcal{A}.length)
class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        vector<int> bmax = count("");
        for (const string& b : words2) {
            vector<int> bCount = count(b);
            for (int i = 0; i < 26; ++i) {
                bmax[i] = max(bmax[i], bCount[i]);
            }
        }

        vector<string> ans;
        for (const string& a : words1) {
            vector<int> aCount = count(a);
            bool isUniversal = true;
            for (int i = 0; i < 26; ++i) {
                if (aCount[i] < bmax[i]) {
                    isUniversal = false;
                    break;
                }
            }
            if (isUniversal) {
                ans.push_back(a);
            }
        }

        return ans;
    }

private:
    vector<int> count(const string& S) {
        vector<int> ans(26, 0);
        for (char c : S) {
            ans[c - 'a']++;
        }
        return ans;
    }
};

GPT (o3-mini-high)

이 코드는 두 문자열 배열 words1과 words2가 주어졌을 때, words2의 모든 단어를 “부분 집합”으로 포함하는 words1의 단어들을 찾아 반환하는 문제(LeetCode의 Word Subsets)의 풀이입니다.
즉, words1의 단어 a가 “유니버설”하다는 것은, words2에 있는 모든 단어 b에 대해, b에 등장하는 각 문자가 a에도 적어도 동일한 빈도로 등장한다는 의미입니다.

아래에서 코드의 각 부분과 동작 방식을 자세히 설명합니다.

1. wordSubsets 함수 개요

vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
    vector<int> bmax = count("");  // 26개의 0으로 초기화된 벡터
    for (const string& b : words2) {
        vector<int> bCount = count(b);
        for (int i = 0; i < 26; ++i) {
            bmax[i] = max(bmax[i], bCount[i]);
        }
    }

    vector<string> ans;
    for (const string& a : words1) {
        vector<int> aCount = count(a);
        bool isUniversal = true;
        for (int i = 0; i < 26; ++i) {
            if (aCount[i] < bmax[i]) {
                isUniversal = false;
                break;
            }
        }
        if (isUniversal) {
            ans.push_back(a);
        }
    }

    return ans;
}

Step 1: words2의 문자 빈도수 최대값 계산

  • 목적:
    words2에 포함된 모든 단어들이 필요로 하는 최소한의 문자 빈도를 하나의 벡터 bmax에 저장합니다.

  • 동작 방식:

    1. vector<int> bmax = count("");
      → count("") 함수는 26개의 0으로 채워진 벡터를 반환합니다.
    2. words2의 각 단어 b에 대해:
      • vector<int> bCount = count(b);
        → 단어 b의 각 문자('a'부터 'z')의 등장 횟수를 담은 벡터를 구합니다.
      • 각 문자에 대해 bmax[i] = max(bmax[i], bCount[i]);
        → 모든 단어 b 중에서, 각 문자에 대해 가장 많이 등장한 횟수를 bmax에 저장합니다.

    이렇게 구한 bmax는 words1의 각 단어가 가져야 할 최소 문자 빈도를 나타냅니다.
    예를 들어, words2에 "lo", "eo"가 있다면,

    • "lo"는 l:1, o:1
    • "eo"는 e:1, o:1
      → 최종 bmax는 e:1, l:1, o:1 (나머지 문자는 0)이 됩니다.

2. words1의 단어들이 유니버설한지 검사

  • 목적:
    words1의 각 단어 a에 대해,
    a의 문자 빈도수(aCount)가 bmax에 저장된 최소 빈도를 만족하는지 검사합니다.

  • 동작 방식:

    1. vector<string> ans;
      → 결과를 담을 문자열 벡터를 초기화합니다.
    2. words1의 각 단어 a에 대해:
      • vector<int> aCount = count(a);
        → a의 각 문자가 몇 번 등장하는지 카운트합니다.
      • 26개의 문자 각각에 대해 if (aCount[i] < bmax[i]) 조건을 확인합니다.
        → 만약 a가 어떤 문자의 빈도가 부족하면 isUniversal을 false로 만들고 반복문을 종료합니다.
      • 만약 모든 문자를 만족한다면, a는 유니버설 단어이므로 ans에 추가합니다.

  • 최종적으로 ans에 담긴 모든 단어들이 words2의 모든 단어를 부분 집합으로 포함하는 단어들이 됩니다.

3. count 헬퍼 함수

vector<int> count(const string& S) {
    vector<int> ans(26, 0);
    for (char c : S) {
        ans[c - 'a']++;
    }
    return ans;
}

  • 역할:
    주어진 문자열 S에 대해,
    알파벳 'a'부터 'z'까지 각 문자가 몇 번 등장하는지를 저장한 길이 26의 벡터를 반환합니다.

  • 동작 방식:

    1. 26개의 0으로 초기화된 벡터 ans를 생성합니다.
    2. 문자열 S의 각 문자 c에 대해,
      → ans[c - 'a']의 값을 1 증가시킵니다.
    3. 최종적으로 각 문자의 등장 횟수를 담은 벡터를 반환합니다.

4. 전체 동작 요약

  1. words2 처리:
    모든 단어의 문자 빈도를 확인하여, 각 문자가 최소 몇 번 등장해야 하는지 bmax에 기록합니다.

  2. words1 처리:
    각 단어 a에 대해 문자 빈도 벡터 aCount를 계산하고,
    aCount가 bmax의 모든 조건(각 문자의 최소 등장 횟수)을 만족하면 결과 리스트에 추가합니다.

  3. 결과 반환:
    유니버설한 단어들로 구성된 벡터 ans를 반환합니다.

이와 같이, 이 코드는 각 단어의 문자 빈도를 이용하여 문제를 효율적으로 해결합니다.
시간 복잡도는 words2의 전체 문자 수와 words1의 전체 문자 수에 비례하여, 주어진 문제에 적합한 최적화된 풀이입니다.