Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.


Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Example 4:

Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"
Example 5:

Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"
 

Constraints:

1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Amortized analysis

Starter code: class Solution:
    def reverseWords(self, s: str) -> str:
        

Solutions:
class Solution:

	def reverseWords(self, s: str) -> str:
		sLst = s.split()
		reverseStr = ''
		for i in range(len(sLst) - 1, -1, -1):
			if i == len(sLst) - 1:
				reverseStr += sLst[i]
			else:
				reverseStr += ' ' + sLst[i]
		return reverseStr


class Solution:

	def reverseWords(self, s: str) -> str:
		s = s.strip(' ')
		ans = ''
		for segment in s.split(' '):
			if segment == '':
				continue
			ans = segment + ' ' + ans
		return ans[:-1]


class Solution:

	def reverseWords(self, s: str) -> str:
		return ' '.join(s.split()[::-1])


class Solution:

	def reverseWords(self, s: str) -> str:
		s = s.strip().split()
		l = []
		for i in reversed(range(len(s))):
			l.append(s[i])
		return ' '.join(l)


class Solution:

	def reverseWords(self, s: str) -> str:
		curr_word = ''
		ans = []
		for char in s:
			if char == ' ':
				if curr_word != '':
					ans.append(curr_word)
					curr_word = ''
			else:
				curr_word += char
		if curr_word != '':
			ans.append(curr_word)
		return ' '.join(ans[::-1])