Reverse Words in a String

String Simulation

Problem

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.

For example:

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

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

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.

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

Thought Process

• We need to get rid of the leading and trailing spaces

Solution

class Solution:
    def reverseWords(self, s: str) -> str:
        
        n = len(s)  
        i = n-1
        res = ""
        while i >= 0:
            while i >= 0 and s[i] == " ":
                i-=1     
            if i < 0:
                break
            j = i - 1
            while j >= 0 and s[j] != " ":
                j-=1
            sub = s[j+1:i+1]
            if len(res) == 0:
                res = sub
            else:
                res = res + " " + sub
            i = j - 1
        return res
        

Time Complexity

• Time: O(n)

• Space: O(1)