Следующая наша задача - 2559. Count Vowel Strings in Ranges.
📝 Описание задачи
Нам дан массив строк words и массив запросов queries, где каждый запрос задаётся парой [li, ri]. Необходимо для каждого запроса определить количество строк из диапазона [li, ri], которые начинаются и заканчиваются на гласные буквы ('a', 'e', 'i', 'o', 'u').
Вернуть массив ответов, где каждый элемент соответствует результату очередного запроса.
💡 Идея
Чтобы эффективно отвечать на диапазонные запросы, мы можем заранее подсчитать кумулятивные суммы валидных строк (начинающихся и заканчивающихся на гласные) в массиве префиксных сумм. Это позволяет сократить обработку каждого запроса до константного времени.
🔍 Подробности подхода
-
Создание префиксных сумм:
- Сначала создаём итератор
prefix_sum_iter, вычисляющий кумулятивное количество "валидных" строк
(неплохой повод воспользоваться для этого методом std::iter::scan).
- Добавляем
0 в начало итогового массива (см. std::iter::once и std::iter::chain), чтобы упростить расчёты для запросов (исключая лишнюю проверку условий для обработки начала диапазона).
-
Обработка запросов:
- Для каждого запроса
[start, end] результат вычисляется как:
result = prefix_sum[end+1] - prefix_sum[start]
📊 Асимптотика
-
Временная сложность:
O(n+q), где n — количество строк, q — количество запросов:
O(n) для построения префиксных сумм.O(q) для обработки запросов.
-
Пространственная сложность:
O(n) для хранения массива prefix_sum.
💻 Исходный код:
impl Solution {
pub fn vowel_strings(words: Vec<String>, queries: Vec<Vec<i32>>) -> Vec<i32> {
// Create prefix sum iterator
let prefix_sum_iter = words.into_iter().scan(0, |count, word| {
if Self::is_good_word(&word) {
*count += 1;
}
Some(*count)
});
// Collect prefix sum with leading zero for query calculations
let prefix_sum: Vec<_> = std::iter::once(0).chain(prefix_sum_iter).collect();
// Process queries using the precomputed prefix sum
queries.into_iter().map(|query| {
let start = query[0] as usize;
let end = query[1] as usize;
prefix_sum[end + 1] - prefix_sum[start]
}).collect()
}
// Check if a character is a vowel
fn is_vowel(c: char) -> bool {
matches!(c, 'a' | 'e' | 'i' | 'o' | 'u')
}
// Check if a word starts and ends with a vowel
fn is_good_word(word: &str) -> bool {
let bytes = word.as_bytes();
if !bytes.is_empty() {
let first = bytes[0] as char;
let last = bytes[bytes.len() - 1] as char;
Self::is_vowel(first) && Self::is_vowel(last)
} else {
false
}
}
}