Reverse the Word Order
Problem
A sentence holds words separated by one or more spaces, and it may also start or end with spaces. Return a new string with the words in reverse order, joined by exactly one space and with no spaces at either end. A word is any run of characters that are not spaces, and the letters inside a word keep their order.
Examples
Input: s = " the sky is blue "
Output: "blue is sky the"
Why: extra spaces disappear and the words swap placesInput: s = "one"
Output: "one"
Why: a single word has nothing to swap withInput: s = " "
Output: ""
Why: edge case, only spaces means no words at allHints
0 / 3
Reversing the whole string also reverses the letters inside each word, which is not what is asked. The unit that moves is the word.
If you read the sentence from the right end, the words arrive in exactly the order the answer needs.
Start at the last character and walk left. Skip any spaces, then keep walking until the next space to find where the current word begins, and collect that word. Repeat until you pass the start, then join the collected words with single spaces.
Solution
Scanning from the right meets the last word first, so collecting words in the order they are found already produces the reversed sentence. Skipping runs of spaces before each word discards the extra spacing, including spaces at both ends. The letters of each word are sliced out as a block, so they never change order. In everyday Python, joining the reversed result of split gives the same answer in one line. Time is O(n) and space is O(n) for the output.
def reverse_words(s):
words, i = [], len(s) - 1
while i >= 0:
while i >= 0 and s[i] == " ":
i -= 1 # skip the gap before the next word
end = i
while i >= 0 and s[i] != " ":
i -= 1 # walk to the start of that word
if end > i:
words.append(s[i + 1:end + 1])
return " ".join(words)
print(reverse_words(" the sky is blue ")) # -> blue is sky the
print(reverse_words("one")) # -> one
print(reverse_words(" ")) # -> ""Stuck on the idea rather than the code? Reverse Words covers it.