Развернуть строку за O(n)
Реализуйте reverseString(s), возвращающую новую строку с символами s в обратном порядке. Требования: O(n) по времени. reverseString('hello') возвращает 'olleh', а пустая строка возвращает ''.
function reverseString(s) {
// ваш код здесь
}Допишите реализацию.
Разбить на символы, развернуть и склеить: s.split(''), затем .reverse() и .join(''), либо [...s].reverse().join(''). Форма со спредом лучше обрабатывает многобайтовые кодовые точки, чем split(''). Ручной цикл, собирающий результат с последнего индекса вниз, тоже работает за O(n) и возвращает '' для пустой строки.
- ✗Вызывать
reverseпрямо на строке —reverseесть только у массивов - ✗Использовать
split(''), полагая, что он корректно обрабатывает суррогатные пары и эмодзи - ✗Забывать, что строки неизменяемы, поэтому надо вернуть новую строку
- →Почему
[...s]разбивает суррогатные пары корректнее, чемs.split('')? - →Как развернуть порядок слов в предложении, но не буквы внутри них?
Решение
Разбить строку на массив символов, развернуть его и склеить обратно.
function reverseString(s) {
return [...s].reverse().join('');
}Как это работает
Строки в JavaScript неизменяемы, поэтому нельзя развернуть строку на месте — нужно вернуть новую. Спред [...s] создаёт массив символов (корректно обрабатывая суррогатные пары), Array.prototype.reverse переставляет его элементы, а join('') склеивает обратно в строку.
Каждый символ обрабатывается константное число раз, поэтому сложность O(n) по времени. Пустая строка даёт пустой массив, который разворачивается в ''.
