Заменить все пробелы в строке «на месте»
Напишите метод, заменяющий все пробелы в строке символами
%20
. Требуется реализовать алгоритм с заменой «на месте», т.е. без использования дополнительных структур данных. Можно считать, что длина строки позволяет сохранить дополнительные символы.
Разумеется, решить задачу можно с помощью методаreplace
строки, но здесь явно требуется реализовать алгоритм самостоятельно.
Сложность задачи в требовании не использовать дополнительные структуры данных. Иначе, можно просто завести вторую строчку и последовательно копировать все символы из первой, заменив при этом пробелы — так нельзя.
Общий подход к таким задачам — изменять строку, начиная с конца и двигаться к началу. В конце строки можно организовать дополнительное пространство, в котором можно изменять символы и при этом не потерять информацию.
Общая идея алгоритма следующая:
- первым проходом подсчитать количество пробелов
- умножив это значение на 3, получаем количество дополнительных символов в строке
- вторым проходом, который осуществляется с конца строки, выполняется ее модификация: пробел заменяется, а другой символ просто копируется
Т.к. в JavaScript строки неизменяемые, то придется преобразовать строку к массиву и выполнять все манипуляции с ним.
Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.