Задача: 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, которые удовлетворяют этому условию.

😎 Решение:

function wordSubsets($words1, $words2) {
    $maxCount = array_fill(0, 26, 0);

    foreach ($words2 as $word) {
        $count = getCount($word);
        for ($i = 0; $i < 26; $i++) {
            $maxCount[$i] = max($maxCount[$i], $count[$i]);
        }
    }

    $result = [];
    foreach ($words1 as $word) {
        $count = getCount($word);
        if (isUniversal($count, $maxCount)) {
            $result[] = $word;
        }
    }

    return $result;
}

function getCount($word) {
    $count = array_fill(0, 26, 0);
    foreach (str_split($word) as $char) {
        $count[ord($char) - ord('a')]++;
    }
    return $count;
}

function isUniversal($count, $maxCount) {
    for ($i = 0; $i < 26; $i++) {
        if ($count[$i] < $maxCount[$i]) {
            return false;
        }
    }
    return true;
}

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