Reverse a String

Q: Какова временная сложность разворота строки?

Разворот занимает O(n) времени, потому что каждый символ должен переместиться на новую позицию и обрабатывается один раз. Создание новой строки требует дополнительной памяти объёмом O(n) . Для обмена символов с помощью двух указателей требуется лишь O(1) дополнительной памяти, если символы уже находятся в изменяемом массиве.

Q: Как перевернуть строку без встроенной функции reverse?

Скопируйте символы в массив, поместите по одному указателю на каждый конец, поменяйте два символа местами и перемещайте указатели навстречу друг другу, пока они не встретятся. В качестве альтернативы пройдите циклом от последнего индекса до первого и добавьте каждый символ в буфер. Оба способа за один проход создают перевёрнутую строку.

Q: Можешь развернуть строку на месте?

Только если символы находятся в изменяемом буфере, например в массиве char в C, Java или C#, в списке в Python или в std::string в C++. Строки в Java, Python, JavaScript и многих других языках неизменяемы, поэтому их копируют в массив, меняют символы местами внутри него и создают новую строку. Сам шаг обмена символами местами в любом случае выполняется на месте.

Q: Почему цикл с двумя указателями останавливается посередине?

При каждой перестановке два символа занимают свои окончательные позиции, поэтому после n / 2 перестановок каждый символ оказывается на своём месте. Продолжение после середины меняет те же пары обратно и отменяет выполненную работу. Если длина нечётная, средний символ уже находится на зеркальном ему индексе, поэтому его не нужно менять.

НовичокМассивы и строки Два указателя

+10

Тебе дана строка s, состоящая из английских букв и цифр. Верни новую строку с теми же символами в обратном порядке: последний символ должен стать первым, а первый — последним. Сохрани каждый символ в точности таким, какой он есть, включая регистр.

Функция

reverseString(s: string) → string

sstring: строка для разворота
Возвращаетstring: символы s в обратном порядке

Ограничения

1 ≤ s.length ≤ 10⁴
s содержит только английские буквы (a–z, A–Z) и цифры (0–9).

Примеры

Ввод: s = "Coddy2026"
Вывод: "6202yddoC"
Пояснение: Прочитай Coddy2026 от последнего символа к первому: 6, 2, 0, 2, затем y, d, d, o и наконец заглавную C.

Ввод: s = "noon"
Вывод: "noon"
Пояснение: noon — палиндром, поэтому при обратном чтении получается то же слово. Внешние буквы n меняются местами, затем то же самое происходит с двумя буквами o.

+14 скрытых тестов при отправке

Дополнительный вопрос

Как изменить порядок слов в предложении, превратив hello big world в world big hello, сохранив при этом порядок букв в каждом слове?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

У каждого символа есть фиксированное место назначения: символ с индексом i должен находиться по индексу n-1-i. Можно записать символы в новую строку в этом порядке или менять их местами попарно, двигаясь с обоих концов. Именно вариант с обменом местами спрашивают на собеседованиях, потому что тот же приём с двумя указателями разворачивает массив на месте и проверяет, является ли строка палиндромом.

Скопируйте символы с обратной стороны

Идея

Обратная строка для s начинается с последнего символа s, продолжается предпоследним и заканчивается первым. Поэтому перебирай индексы от n-1 до 0 и добавляй каждый символ к ответу по мере его получения. Для Coddy2026 ты добавишь 6, 2, 0, 2, y и так далее, что даст 6202yddoC.

Каждый символ считывается и записывается один раз, поэтому трудоёмкость составляет O(n). Ответ — это вторая строка из n символов, для которой требуется дополнительная память объёмом O(n).

Способ добавления имеет значение. Добавление одного символа к неизменяемой строке с помощью + каждый раз копирует всю строку, и при n = 10^4 это около 5 × 10^7 копирований символов. Собирай символы в список или построитель строк и объединяй их один раз в конце.

Алгоритм

Создай пустой список или построитель строк для ответа.
Перебирай i от n-1 до 0 в обратном порядке.
Добавь s[i] к ответу.
Объедини элементы ответа в строку и верни её.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

Меняйте местами элементы с обоих концов с помощью двух указателей

Идея

При развороте символы объединяются в пары снаружи внутрь. Первый и последний меняются местами, затем второй и предпоследний — и так далее по направлению к середине. Поставь указатель left на индекс 0, а указатель right — на индекс n-1, поменяй местами два символа и сдвинь оба указателя на один шаг к середине.

Остановись, когда указатели встретятся или пересекутся. В строке noon указатели начинают с позиций 0 и 3, затем переходят на позиции 1 и 2, а после этого пересекаются — после двух перестановок. В строке нечётной длины, например xYz, указатели встретятся на среднем символе, который уже находится на своём окончательном месте, поэтому его не затронут. Каждая перестановка ставит два символа на их окончательные места, поэтому для завершения достаточно n / 2 перестановок.

Для самих перестановок нужна лишь одна временная переменная — дополнительная память O(1). Большинство языков не позволяют изменять строку на месте, поэтому сначала нужно скопировать её в массив символов, что требует O(n) памяти. На собеседовании, если на входе уже дан массив символов, этот способ разворачивает его вообще без дополнительной памяти.

Алгоритм

Скопируй s в массив символов.
Установи left = 0 и right = n-1.
Пока left < right, меняй местами символы на позициях left и right, затем прибавь 1 к left и вычти 1 из right.
Преобразуй массив обратно в строку и верни её.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

Ловушки и крайние случаи

Переворачивание выглядит как одна строка кода, но ошибки скрываются в границах циклов и в том, как формируется ответ.

Цикл проходит по left до самого n-1. После середины каждая пара меняется местами второй раз, и строка возвращается к исходному виду. Остановитесь на left < right.
Запуск обратного цикла с n вместо n-1 приводит к чтению за пределами последней позиции. В Lua и R индексы вместо этого идут от 1 до n.
Формирование ответа с помощью result = result + ch для неизменяемой строки. На каждом шаге копируется всё, что уже есть, из-за чего задача с линейной сложностью превращается в квадратичную на длинных входных данных.
Забыть завершающий символ '\0' в C. Буфер размером n байт слишком мал на один байт; выделите n + 1.
Обмен значениями без временной переменной: после chars[left] = chars[right] старый символ слева теряется, если только ваш язык не меняет оба значения местами одновременно.

Частые вопросы4

Какова временная сложность разворота строки?

Разворот занимает O(n) времени, потому что каждый символ должен переместиться на новую позицию и обрабатывается один раз. Создание новой строки требует дополнительной памяти объёмом O(n). Для обмена символов с помощью двух указателей требуется лишь O(1) дополнительной памяти, если символы уже находятся в изменяемом массиве.

Как перевернуть строку без встроенной функции reverse?

Скопируйте символы в массив, поместите по одному указателю на каждый конец, поменяйте два символа местами и перемещайте указатели навстречу друг другу, пока они не встретятся. В качестве альтернативы пройдите циклом от последнего индекса до первого и добавьте каждый символ в буфер. Оба способа за один проход создают перевёрнутую строку.

Можешь развернуть строку на месте?

Только если символы находятся в изменяемом буфере, например в массиве char в C, Java или C#, в списке в Python или в std::string в C++. Строки в Java, Python, JavaScript и многих других языках неизменяемы, поэтому их копируют в массив, меняют символы местами внутри него и создают новую строку. Сам шаг обмена символами местами в любом случае выполняется на месте.

Почему цикл с двумя указателями останавливается посередине?

При каждой перестановке два символа занимают свои окончательные позиции, поэтому после n / 2 перестановок каждый символ оказывается на своём месте. Продолжение после середины меняет те же пары обратно и отменяет выполненную работу. Если длина нечётная, средний символ уже находится на зеркальном ему индексе, поэтому его не нужно менять.

Python

def reverseString(s):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "Coddy2026"

Ожидается

"6202yddoC"