Сегодня мы разберём задачу 916. Word Subsets.
📝 Описание задачи
Вам даны два массива строк words1 и words2.
Задача: найти все строки из words1, которые являются универсальными относительно всех строк из words2.
Условие универсальности:
Строка a из words1 универсальна, если для каждой строки b из words2 строка b является подмножеством строки a (Подмножество строки: строка b является подмножеством строки a, если каждая буква в b встречается в a как минимум столько же раз).
Пример:
["warrior", "world"] и ["wrr"]
Ответ: ["warrior"], так как только warrior покрывает все буквы из wrr.
💡 Идея
Для эффективного решения задачи:
- Определим максимальное количество вхождений каждой буквы по всем строкам из words2.
- Для каждой строки из words1 проверим, удовлетворяет ли она этим требованиям.
🔍 Детали подхода
-
Предварительные вычисления:
- Для строк из
words2 вычисляем частотный массив (массив частот букв) и сохраняем максимальные частоты для каждой буквы.
- Это позволяет объединить требования всех строк из
words2 в одну структуру данных.
-
Фильтрация строк из words1:
- Проверяем длину строки (быстрая фильтрация).
- Вычисляем частотный массив для строки и сравниваем его с максимальными частотами из шага 1.
-
Возврат результата:
- Все строки, удовлетворяющие условиям, добавляем в результат.
📊 Асимптотика
- Временная сложность:
O(N+M), где:
N — суммарная длина всех строк из words2 (предварительные вычисления).
M — суммарная длина всех строк из words1 (фильтрация).
- Пространственная сложность:
O(m)
O(26) — память для промежуточных массивов частот.
O(m) — для результата, где m — количество строк в words1.
📄 Код решения
impl Solution {
pub fn word_subsets(words1: Vec<String>, words2: Vec<String>) -> Vec<String> {
// Calculate the maximum frequency required for each letter from words2.
let mut combined_frequencies = [0; 26];
for word in &words2 {
let word_frequencies = Solution::calc_frequencies(word);
for i in 0..26 {
combined_frequencies[i] = combined_frequencies[i].max(word_frequencies[i]);
}
}
// Calculate the minimum universal length based on combined frequencies.
let min_universal_len: usize = combined_frequencies.iter().sum();
// Filter universal words from words1.
words1.into_iter()
.filter(|word|
word.len() >= min_universal_len && Solution::is_universal(word, &combined_frequencies)
).collect()
}
// Helper function to calculate the frequency of each letter in a given word.
fn calc_frequencies(word: &str) -> [usize; 26] {
let mut frequencies = [0; 26];
for ch in word.chars() {
frequencies[(ch as u8 - b'a') as usize] += 1;
}
frequencies
}
// Helper function to check if a word satisfies the required frequencies.
fn is_universal(word: &str, required_frequencies: &[usize; 26]) -> bool {
let word_frequencies = Self::calc_frequencies(word);
word_frequencies.into_iter()
.zip(required_frequencies.iter())
.all(|(freq_in_word, &freq_required)| freq_in_word >= freq_required)
}
}