Find a word's two ends
Walk from the end, marking where each word starts and stops. About 9 minutes.
A word is the stretch between spaces
Messages copied from the web often come with messy spacing: extra spaces at the start, two spaces between words. You want the words themselves, in reverse order, tidily separated by single spaces.
A word is simply a stretch of non-space characters. To pull one out: skip over any spaces, note where the word ends, then keep walking until you hit a space or the edge. Everything in between is the word.
- words
- []
The last box is a space. Skip spaces until we land on a letter.
Walk from the back
If you walk the sentence from the last character to the first, you meet the words last-first, which is exactly the reversed order you want. Collect each word as you find it and join them with single spaces at the end.
Because spaces are skipped before a word is marked, extra spaces never create empty words.
words = []
i = len(s) - 1
while i >= 0:
while i >= 0 and s[i] == " ":
i -= 1
end = i
while i >= 0 and s[i] != " ":
i -= 1
if end >= 0:
words.append(s[i + 1:end + 1])
return " ".join(words)Walking back through "hi there " (with spaces), which word is found first?
- Athere
- Bhi
- CAn empty word
Show the answer
there. After skipping the trailing space, the walk lands in "there".
Reverse the words
You get a sentence of words separated by spaces, possibly with extra spaces at the ends or between words. Return the words in reverse order, joined by single spaces, with no spaces at the ends.
s = " the sky is blue " → "blue is sky the"
0 ≤ length ≤ 100,000 · letters, digits and spaces