Reverse Words in a String

Q: Какова временная сложность алгоритма Reverse Words in a String?

Оба подхода выполняются за время O(n) для строки длины n , поскольку каждый символ считывается и записывается ограниченное число раз. Разбиение требует O(n) дополнительной памяти для списка слов. Переворот всей строки, а затем каждого слова требует O(1) дополнительной памяти при работе с массивом символов, который можно изменять.

СреднеМассивы и строки Два указателя

+10

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

Верни слова в обратном порядке, разделив их ровно одним пробелом, без пробелов в начале и в конце. Написание каждого слова остается неизменным; меняется только порядок слов.

Функция

reverseWords(s: string) → string

sstring: буквы, цифры и пробелы, содержащие как минимум одно слово
Возвращаетstring: слова s в обратном порядке, разделённые одиночными пробелами

Ограничения

1 ≤ s.length ≤ 10⁴
s содержит только английские буквы, цифры и пробелы.
s содержит как минимум одно слово.

Примеры

Ввод: s = "Coddy runs in 15 languages"
Вывод: "languages 15 in runs Coddy"
Пояснение: Слова — это Coddy, runs, in, 15 и languages. Если читать их с последнего до первого, они дают languages 15 in runs Coddy; 15 считается словом, потому что слова могут содержать цифры.

Ввод: s = " practice makes progress "
Вывод: "progress makes practice"
Пояснение: Пробелы с обоих концов удаляются, а последовательности из двух и трёх пробелов между словами сокращаются до одного. Три слова выводятся в обратном порядке: progress makes practice.

Ввод: s = " single "
Вывод: "single"
Пояснение: Список из одного слова читается одинаково в обратном порядке. Исчезают только пробелы вокруг него, поэтому ответ — single.

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

Можешь перевернуть слова, но сохранить пробелы в s: те же последовательности пробелов, той же длины и в том же порядке?

Решение

Порядок слов — это один разворот; именно пробелы приводят к ошибкам в решениях. Пробелы в начале и в конце, а также повторяющиеся пробелы между словами должны исчезнуть: в ответе между словами должен быть ровно один пробел. Можно разбить строку на список слов или развернуть всю строку, а затем каждое слово внутри одного массива.

Разделите на слова и соедините их в обратном порядке

Идея

Разбейте s на слова, разверните список и объедините его, используя одиночные пробелы. При разбиении нужно быть внимательным: если разделить " practice makes progress " по каждому пробелу, получится шесть пустых элементов вокруг трёх слов. Удалите пустые элементы, и в списке останутся practice, makes, progress.

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

Алгоритм

Разделите s по пробелам.
Пропустите пустые элементы.
Переверните список слов.
Объедините слова, поставив между ними по одному пробелу, и верните результат.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Переверните всю строку, а затем каждое слово

Идея

Переворот всей строки ставит слова в правильном порядке, но написание каждого слова оказывается перевёрнутым: Coddy runs in 15 languages превращается в segaugnal 51 ni snur yddoC. Затем отдельный переворот каждого слова даёт languages 15 in runs Coddy.

Пробелы обрабатываются за тот же проход. Индекс read проходит по перевёрнутому массиву и пропускает пробелы; индекс write указывает, куда поместить следующий сохранённый символ. Копирование никогда не перезаписывает символ, который ещё нужен, потому что write никогда не опережает read: один пробел, записанный перед словом, заменяет как минимум один пробел, пропущенный индексом read.

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

Алгоритм

Скопируй s в массив символов и разверни весь массив.
Пройди по массиву с помощью индекса чтения, пропуская пробелы.
Для каждого слова сначала запиши один пробел, если только это не первое слово, затем скопируй символы слова по индексу записи.
Разверни скопированный фрагмент, чтобы слово читалось в прямом порядке.
Верни первые write символов.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

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

Разделение по одному пробелу с сохранением каждой части. "a b" разбивается на a, пустую часть и b, а при объединении два пробела возвращаются: "b a".
Расчёт на то, что разделение отбросит пустые части по краям. Метод Java split(" ") отбрасывает пустые части в конце, но сохраняет их в начале, поэтому " a b" всё ещё оставляет одну пустую часть.
Добавление пробела после каждого слова, включая последнее, из-за чего ответ заканчивается пробелом. Ставьте пробел перед каждым словом, кроме первого.
Выполнение только одного разворота в версии с изменением на месте. Разворот только слов даёт yddoC snur ni 51 segaugnal.
В PHP и R ввод, состоящий только из цифр, например 2026, может быть получен как число. Преобразуйте его в строку перед разделением.

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

Какова временная сложность алгоритма Reverse Words in a String?

Оба подхода выполняются за время O(n) для строки длины n, поскольку каждый символ считывается и записывается ограниченное число раз. Разбиение требует O(n) дополнительной памяти для списка слов. Переворот всей строки, а затем каждого слова требует O(1) дополнительной памяти при работе с массивом символов, который можно изменять.

Как обрабатывать несколько пробелов между словами?

Считай словом последовательность символов без пробелов и никогда не копируй пробелы из входных данных. Разбиение без разделителя в Python и Ruby, strings.Fields в Go и split_whitespace в Rust уже пропускают каждую последовательность пробелов и пробелы по краям; в остальных случаях отбрасывай пустые части. Затем ставь между словами по одному пробелу.

Можешь перевернуть слова без функции split?

Да. Просканируй строку справа налево: пропускай пробелы, отмечай конец слова, двигайся влево к его началу и добавляй слово, ставя перед ним пробел, если оно не первое. Каждый символ посещается один раз, поэтому время выполнения остаётся равным O(n), а слова выводятся в обратном порядке без списка, который нужно переворачивать.

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

Тест #1

Тест #2

Тест #3

Аргумент

s = "Coddy runs in 15 languages"

Ожидаемый вывод

"languages 15 in runs Coddy"