Reverse Words in a String

Средняя№151справа налево

Дана строка из слов, разделённых пробелами. Нужно вернуть те же слова в обратном порядке: между словами ровно один пробел, в начале и в конце — ни одного, даже если в строке там или между словами лишние пробелы. Наш пример: «␣red␣␣fox␣», где ␣ — пробел, ответ — «fox red».

151 Reverse Words in a StringРазбор · 1×

Пример: «␣red␣␣fox␣» (␣ — пробел). Оба указателя идут с правого конца: end перешагивает пробелы до конца слова, start находит, где это слово начинается.

0␣1r2e3d4␣5␣6f7o8x9␣
ещё не прочитанычитаем сейчасслово взятопробел пропущен

words — пустой список: сюда слова попадут сразу в нужном порядке

01/36
сначала · назад · пуск · шаг
Скорость
1function reverseWords(s):
2 words = []
3 end = len(s) - 1
4 while end >= 0:
5 if s[end] == " ":
6 end = end - 1
7 else:
8 start = end
9 while start > 0 and s[start - 1] != " ":
10 start = start - 1
11 words.add(s[start..end])
12 end = start - 1
13 return join(words, " ")
состояние
end
–
start
–
s[end]
–
words
[]
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

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

  1. Если читать с конца, первым найдётся последнее слово строки. Значит, слова сразу идут в том порядке, который нужен в ответе, и потом ничего разворачивать не нужно.
  2. Пробелы в ответ не попадают: end их перешагивает, а берём только целые слова. Одиночные пробелы появляются, когда склеиваем слова, поэтому лишние пробелы в начале, в конце и между словами пропадают сами.
  3. После слова end сразу прыгает левее него, поэтому ни один символ не читается дважды.

Сложность

Время O(n): оба указателя идут только влево, end проходит пробелы, а start — буквы, поэтому каждый символ проходится один раз. Память O(n): список слов и ответ занимают до n символов.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.