Ссылка на задачу – 3174. Clear Digits.
📌 Описание задачи
Дана строка s, содержащая буквы и цифры. Из неё возможно удалять цифры только путем выполнения следующей операции:
- Удалить первую найденную цифру и ближайший нецифровой символ слева.
Вернуть итоговую строку после итеративного выполнения указанной операции до исчезновения всех цифр.
💡 Идея
Достаточно легко придумать алгоритм, формирующий ответ справа-налево (просто запоминаем, сколько символов нужно скипнуть после встреченных цифр).
Мы же реализуем решение с прямым (слева-направо) обходом строки без необходимости переворачивания результата.
- Используем буфер (
buffer) для хранения промежуточного результата.
- Используем указатель
write_index, который отслеживает место для записи следующего символа.
- При встрече цифры уменьшаем
write_index (удаляем ближайший нецифровой символ).
⚙ Подробности подхода
- Инициализируем буфер размером
s.len() (заполняем заглушками '\0').
- Проходим по строке слева направо:
- Если
c — цифра, уменьшаем write_index
(saturating_sub(1) защищает от выхода за границы).
- Если
c — не цифра, записываем его в buffer[write_index]
и увеличиваем write_index.
- Возвращаем
buffer[..write_index] как итоговую строку.
⏳ Асимптотика
- Временная сложность:
O(n) – Один проход по s без дополнительных итераций.
- Дополнительная память:
O(n) – Буфер хранит промежуточный результат, но без лишних аллокаций.
📝 Исходный код
impl Solution {
pub fn clear_digits(s: String) -> String {
let mut buffer = vec!['\0'; s.len()]; // Preallocate buffer with placeholders
let mut write_index = 0 as usize; // Tracks position to write valid characters
for c in s.chars() {
if c.is_ascii_digit() {
write_index = write_index.saturating_sub(1); // Remove the last non-digit
} else {
buffer[write_index] = c; // Store valid character
write_index += 1;
}
}
buffer[..write_index].iter().collect() // Collect valid portion into final string
}
}
Tags: #rust #algorithms #strings