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.

&nbsp;
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.


&nbsp;
Constraints:


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


&nbsp;
Follow-up:&nbsp;If the string data type is mutable in your language, can&nbsp;you solve it&nbsp;in-place&nbsp;with&nbsp;O(1)&nbsp;extra space?

class Solution:
    def split(self, s: str, delimiter=" ") -> List[str]:
        start, end = 0, 0

        res = []
        for ch in s:
            if ch == delimiter:
                if start == end:
                    start += 1
                else:
                    res.append(s[start:end])
                    start  = end + 1
            
            end += 1
        
        if start != end:
            res.append(s[start:end])

        return res

    def reverse_list(self, ll: List[str]) -> List[str]:
        l, r = 0, len(ll) - 1

        while l < r:
            ll[l], ll[r] = ll[r], ll[l]
            l += 1
            r -= 1
        
        return ll

    def reverseWords(self, s: str) -> str:

        # split first
        splitted_str_list = self.split(s)

        # reverse splitted list
        reversed_str_list = self.reverse_list(splitted_str_list)

        # join an return
        return " ".join(reversed_str_list)
class Solution {
    public String reverseWords(String s) {
        String[] arr = s.replaceAll("\\s{2,}", " ").split(" "); 
        // splitting based on while spaces by replaceing spaces by single gap 
        int n = arr.length;
        String temp = "";
        for(int i =0;i<n/2;i++){
            temp = arr[i];
            arr[i] = arr[n-i-1];
            arr[n-i-1]=temp;
        }
        String result ="";
        for(int i =0;i<n-1;i++){
            result+=arr[i]+" ";
        }
        result+=arr[n-1];
        return result.trim();
        
    }
}
class Solution {
public:
    string reverseWords(string s) {
        int i=0;
        string res = "";
        while(i<s.length())
        {
            while(i<s.length() && s[i]==' ')
                i++;

            if(i>=s.length())
                break;

            int j=i+1;

            while(j<s.length() && s[j]!=' ')
                j++;

            string tmp = s.substr(i,j-i);
            if(res.length()==0)
            {
                res = tmp;
            }
            else
            {
                res = tmp + " " + res;
            }
            i=j+1;
        }
        return res;
    }
};
var reverseWords = function(s) {
    return s.split(" ").filter(i => i).reverse().join(" ");
};
Reverse Words in a String