Задача: 916. Word Subsets
Сложность: medium

Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.

Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

👨‍💻 Алгоритм:

1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.

2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2.

3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.

😎 Решение:

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        vector<int> maxCount(26, 0);
        for (const string& word : words2) {
            vector<int> count = getCount(word);
            for (int i = 0; i < 26; ++i) {
                maxCount[i] = max(maxCount[i], count[i]);
            }
        }

        vector<string> result;
        for (const string& word : words1) {
            vector<int> count = getCount(word);
            if (isUniversal(count, maxCount)) {
                result.push_back(word);
            }
        }
        
        return result;
    }

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

    bool isUniversal(const vector<int>& count, const vector<int>& maxCount) {
        for (int i = 0; i < 26; ++i) {
            if (count[i] < maxCount[i]) {
                return false;
            }
        }
        return true;
    }
};

Ставь 👍 и забирай 📚 Базу знаний