151. Reverse Words in a String

Description:

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.

 

'''
[1] built-in library method solution)

return ' '.join(reversed(s.split()))

- T/C: O(n)  # for spliting O(n), for reversing O(n), and joining O(n)
- S/C: O(1)  
'''

'''
[2] using stack)

stack=[]
tmp_str=''

for c in s:
    if c ==' ':
        if tmp_str != '':
            stack.append(tmp_str[:])
            tmp_str=''
        continue
    else:
        tmp_str+=c

if tmp_str !='':
    stack.append(tmp_str[:])

return " ".join(reversed(stack))    # if not using python, answer+=stack.pop(), while !stack.emtpy()

- T/C: O(n) # for one-pass and reversed()
- S/C: O(n) # for stack
'''


class Solution:
    def reverseWords(self, s: str) -> str:
        stack=[]
        tmp_str=''

        for c in s:
            if c ==' ':
                if tmp_str != '':
                    stack.append(tmp_str[:])
                    tmp_str=''
                continue
            else:
                tmp_str+=c

        if tmp_str !='':
            stack.append(tmp_str[:])

        return " ".join(reversed(stack))