Новый день - новая задача 2109. Adding Spaces to a String.
Условие 🧩
Дана строка s и массив индексов spaces. Нужно добавить пробелы перед символами строки, расположенными по данным индексам, и вернуть новую строку. Например, для s = "EnjoyYourCoffee" и spaces = [5, 9] результатом будет "Enjoy Your Coffee".
Если решать абы как, то можно и в ней запутаться в индексах. Мы же будем делать все максимально просто.
Идея решения 🧠
Вместо создания промежуточных строк или модификации исходной строки, мы используем построение строки с выделением памяти заранее, чтобы минимизировать накладные расходы.
Подход 🔍
- Предварительно выделяем память для результирующей строки с помощью
String::with_capacity, учитывая длину строки и количество пробелов.
- Проходим по массиву индексов spaces:
- Добавляем в результат подстроку от предыдущей позиции до текущего индекса.
- Добавляем пробел.
- После цикла добавляем оставшуюся часть строки.
- Возвращаем итоговую строку.
Анализ сложности 📊
- Временная сложность:
O(n), где n=длина строки+количество пробелов. Все операции выполняются за один проход.
- Пространственная сложность:
O(n), поскольку результирующая строка создаётся с заранее выделенной памятью.
Исходный код решения
impl Solution {
pub fn add_spaces(s: String, spaces: Vec<i32>) -> String {
let mut result = String::with_capacity(s.len() + spaces.len()); // Pre-allocate capacity for efficiency
let mut word_pos = 0;
for &space_pos in &spaces {
let space_pos = space_pos as usize; // Convert i32 to usize for indexing
result.push_str(&s[word_pos..space_pos]); // Add the substring
result.push(' '); // Add the space
word_pos = space_pos;
}
result.push_str(&s[word_pos..]); // Add the remaining substring
result
}
}
Ещё один простой вариант решения - собрать все слайсы, отвечающие словам в одну коллекцию и проджойнить стандартными средствами через пробел.
impl Solution {
pub fn add_spaces(s: String, spaces: Vec<i32>) -> String {
// Convert indices to usize
let mut spaces: Vec<usize> = spaces.into_iter().map(|s_pos| s_pos as usize).collect();
// Add the start (0) and end (s.len()) boundaries to spaces
spaces.insert(0, 0);
spaces.push(s.len());
// Create slices from spaces indices
let slices: Vec<&str> = spaces.windows(2)
.map(|window| &s[window[0]..window[1]])
.collect();
// Join the slices with spaces
slices.join(" ")
}
}
В этом коде есть один грустный момент - необходимость создания промежуточного вектора из слайсов исходной строки.
К сожалению, join из стандартной библиотеки позволяет только такое использование.
Но, если мы не ограничеы стандартной библиотекой, то крейт itertools спешит нам на помощь ;)
ответить