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

Constraints:

• 1 <= s.length <= 10^4

• s contains English letters (upper-case and lower-case), digits, and spaces ' '.

• There is at least one word in s.

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"

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

💡 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

class Solution {
    /**
     * @time  : O(n), n is the length of input string
     * @space : O(m), m is the number of words in the input string
     */
    
    public String reverseWords(String s) {
        int l = 0, r = s.length() - 1;
        while(l <= r && s.charAt(l) == ' ') ++l;
        while(l <= r && s.charAt(r) == ' ') --r;

        Deque<String> d = new ArrayDeque();
        StringBuilder word = new StringBuilder();
        
        while(l <= r) {
            char c = s.charAt(l);

            if((word.length() != 0) && (c == ' ')) {
                d.offerFirst(word.toString());
                word.setLength(0);
            } else if(c != ' ') {
                word.append(c);
            }
            ++l;
        }
        
        d.offerFirst(word.toString());
        return String.join(" ", d);
    }
}