Код Senior Два указателя обновлено
Строки с забоем
Условие
Символ '#' означает забой. Равны ли строки после применения забоев? Дополнительной памяти под строки не выделяй.
Примеры
backspaceCompare("ab#c", "ad#c") // true
backspaceCompare("ab##", "c#d#") // true
backspaceCompare("a#c", "b") // false
Как подойти
Прямолинейное решение со стеком тратит O(n) памяти. Проход с конца с счётчиком забоев даёт O(1): с конца видно, сколько символов будет удалено, а слева направо - нет. Условие выхода надо писать аккуратно, чтобы разная длина не проходила как равенство.
Подсказки: 2
- Идти надо с конца: только так известно, сколько символов съедено.
- Считай накопленные забои и пропускай ровно столько символов.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.