Given a string s made of words separated by spaces, return a string with the words in reverse order, joined by single spaces. A word is any run of non-space characters. The input may have leading, trailing or repeated spaces between words, but the output must have none of them.
- 1 <= s.length <= 10^4
- `s` contains English letters, digits and spaces
- `s` has at least one word
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The simplest correct idea is to collect the words and join them in reverse, which is O(n) time and space. In interviews you may be asked to do it by hand: walk from the end of the string, skip spaces, then mark the end of a word and move left until its start. Append that word to a builder with one space between words. Every character is visited a constant number of times.
Algorithm
- Set
i = n - 1and an empty list of words. - Skip spaces while
s[i] == " ". - Mark
end = i, then moveileft whiles[i]is not a space. - Add
s[i+1 .. end]to the words, and repeat untili < 0. - Join the words with single spaces.
O(n)Space: O(n) for the outputclass Solution: def reverseWords(self, s: str) -> str: words = [] i = len(s) - 1 while i >= 0: while i >= 0 and s[i] == ' ': i -= 1 # skip spaces if i < 0: break end = i while i >= 0 and s[i] != ' ': i -= 1 # find the word start words.append(s[i + 1:end + 1]) return ' '.join(words)