Reverse Words in a String

Medium#151from the right end

You get a string of words separated by spaces. Return the same words in reverse order, with exactly one space between them and none at the start or the end — even if the string has extra spaces there or between the words. Our example: "␣red␣␣fox␣", where ␣ is a space — the answer is "fox red".

151 Reverse Words in a StringWalkthrough · 1×

Example: "␣red␣␣fox␣" (␣ is a space). Both pointers walk from the right end: end steps over spaces to the end of a word, start finds where that word begins.

0␣1r2e3d4␣5␣6f7o8x9␣
not read yetbeing readword takenspace skipped

words starts empty: the words go here in the order the answer needs

01/36
restart · back · play · step
Speed
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, " ")
state
end
–
start
–
s[end]
–
words
[]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Reading from the end, the first word found is the last word of the string. So the words come out already in the order the answer needs, and nothing has to be reversed afterwards.
  2. Spaces never go into the answer: end steps over them, and only whole words are taken. The single spaces come from joining the words, so extra spaces at the start, at the end and between the words disappear by themselves.
  3. After a word, end jumps straight to the left of it, so no character is read twice.

Complexity

Time O(n): both pointers only move left, end passes the spaces and start the letters, so each character is passed once. Memory O(n): the list of words and the answer hold up to n characters.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.