Разбор LeetCode 151: реверс слов в строке на Python

Зачем разбирать задачу LeetCode 151?

Задача LeetCode 151 — Reverse Words in a String — на первый взгляд кажется простой вариацией на тему реверса строки. Но как только вы сталкиваетесь с пробелами — ведущими, хвостовыми и множественными между словами — всё усложняется. Эта задача проверяет не только знание синтаксиса, но и умение работать со строками в Python, а также понимание сложности алгоритмов. Разберём два подхода: простой с использованием стандартных методов и более эффективный — с ручной обработкой пробелов. Вы узнаете, как правильно чистить пробелы и почему это важно для собеседований.

Условие задачи и ключевые сложности

Дана строка s, состоящая из слов, разделённых пробелами. Нужно вернуть строку, в которой слова идут в обратном порядке, но сами слова не перевёрнуты. Например, из "the sky is blue" должно получиться "blue is sky the". Основная сложность — пробелы: они могут быть в начале, в конце и между словами может быть несколько пробелов. В выходной строке должен быть ровно один пробел между словами, и никаких пробелов в начале или конце.

Подход 1: split, reverse, join

Самый простой способ — использовать встроенные методы Python. Метод split() без аргумента разбивает строку по любым пробелам (включая табуляцию и переносы) и автоматически удаляет пустые элементы. Это решает проблему лишних пробелов.

def reverse_words(s):
    words = s.split()  # разбиваем по пробелам, игнорируем лишние
    left, right = 0, len(words) - 1
    while left < right:
        words[left], words[right] = words[right], words[left]
        left += 1
        right -= 1
    return ' '.join(words)

Здесь split() делает всю грязную работу: убирает ведущие и хвостовые пробелы, схлопывает множественные. Затем мы переворачиваем список слов с помощью двух указателей (классический паттерн) и соединяем обратно с одним пробелом. Всё просто и элегантно.

Почему это работает?

Метод split() без аргумента использует str.split() с разделителем None, что означает «любая последовательность пробельных символов». Это гарантирует, что в результате не будет пустых строк. Например, " the sky is blue ".split() вернёт ['the', 'sky', 'is', 'blue'].

Сложность по времени — O(n), где n — длина строки. По памяти — O(n) из-за создания списка слов и строки результата. Для большинства случаев этого достаточно.

Подход 2: реверс всей строки и реверс слов

Этот подход — классический ответ на собеседовании, когда спрашивают про оптимизацию памяти. Идея: сначала перевернуть всю строку, затем перевернуть каждое слово обратно. Это позволяет работать с изменяемым списком символов и избежать множества промежуточных строк.

Почему это работает?

Если перевернуть всю строку, то порядок слов станет правильным, но буквы в каждом слове будут в обратном порядке. Например, "the sky" → "yks eht". Затем мы проходим по строке и переворачиваем каждое слово обратно, получая "sky the".

Но сначала нужно сжать пробелы. В Python строки неизменяемы, поэтому мы преобразуем строку в список символов, который можно менять. Используем два указателя: write (куда записываем) и read (откуда читаем). Это паттерн «читающий и пишущий указатели».

def reverse_words(s):
    chars = list(s)
    n = len(chars)

    # Шаг 1: сжатие пробелов
    write = 0
    read = 0
    while read < n:
        # пропускаем пробелы
        while read < n and chars[read] == ' ':
            read += 1
        if read == n:
            break
        # добавляем один пробел перед словом (кроме первого)
        if write != 0:
            chars[write] = ' '
            write += 1
        # копируем слово
        while read < n and chars[read] != ' ':
            chars[write] = chars[read]
            write += 1
            read += 1

    # обрезаем до фактической длины
    chars = chars[:write]
    n = write

    # Шаг 2: переворачиваем всю строку
    reverse(chars, 0, n - 1)

    # Шаг 3: переворачиваем каждое слово
    start = 0
    for i in range(n + 1):
        if i == n or chars[i] == ' ':
            reverse(chars, start, i - 1)
            start = i + 1

    return ''.join(chars)

def reverse(arr, left, right):
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

Разберём по шагам:

1. Сжатие пробелов: указатель read идёт по строке, пропуская все пробелы. Когда находим слово, записываем его в позицию write. Если это не первое слово, перед ним ставим один пробел. Так мы убираем лишние пробелы.
2. Полный реверс: переворачиваем весь список символов.
3. Реверс каждого слова: проходим по строке, находим границы слов (по пробелам) и переворачиваем каждое слово отдельно.

Сложность и память

Время — O(n). Память — O(n) из-за преобразования в список. Но в языках с изменяемыми строками (например, C++) этот алгоритм использует O(1) дополнительной памяти. В Python же мы вынуждены создавать список, поэтому строго O(1) не получится. Однако этот подход всё равно эффективнее, так как создаёт меньше промежуточных объектов.

Сравнение подходов

Оба подхода имеют сложность O(n) по времени и памяти, но отличаются количеством аллокаций. Первый подход создаёт список слов и новую строку при join — это несколько выделений памяти. Второй подход создаёт один список символов и затем одну строку — меньше мусора для сборщика. На собеседовании важно уметь объяснить оба и показать понимание компромиссов.

Практический вывод: что делать прямо сейчас

Откройте LeetCode, найдите задачу 151 и решите её обоими способами. Сначала напишите простое решение с split() и join(), затем попробуйте реализовать алгоритм с реверсом всей строки и слов. Протестируйте на примерах с лишними пробелами. Убедитесь, что оба решения проходят все тесты. Затем попробуйте объяснить разницу в памяти и времени. Это поможет вам на реальных собеседованиях, где часто просят оптимизировать решение.