0151. Reverse Words in a String

Medium | String + Stack | 8 ms (99.84%), 13.9 MB (43.36%)

❓ Problem Statement

Source: LeetCode - Reverse Words in a String GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

💡 Ideas

1. Extract words from the input string (stored in an array)

2. Retrieve words reversely and append to the returned string

🤖 Python3

class Solution:
    def reverseWords(self, s: str) -> str:
        
        # ==================================================
        #  String                                          =
        # ==================================================
        # time  : O(n), n is the length of s
        # space : O(m), m is the number of words in s
        
        l, r = 0, len(s) - 1
        while s[l] == ' ': l += 1
        while s[r] == ' ': r -= 1
            
        words, word = [], ''
        while l <= r:
            if s[l] == ' ':
                if word: words.append(word)
                word = ''
                l += 1
                continue
                
            word += s[l]
            l += 1
        
        if word: words.append(word)
        
        ans = ''
        for i in range(len(words)-1, -1, -1):
            ans += words[i] + ' '
            
        return ans[:-1]
    
    '''
    def reverseWords(self, s: str) -> str:
        return ' '.join( reversed( s.split() ) )
    '''

🤖 Java