116просмотров
8.1%от подписчиков
24 февраля 2026 г.
statsScore: 128
Задача: 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;
} Ставь 👍 и забирай 📚 Базу знаний