https://leetcode.com/problems/reverse-words-in-a-string

If you use python, this problem becomes not medium, but rather easy: all you need to do is to split() you data and take elements in negative order. split() is smart enough to ignore several spaces in a row as well as extra spaces in the begin and in the end.

Complexity: both time and memory complexity is O(n), because we traverse all string and we create new with size O(n).

class Solution:
    def reverseWords(self, s):
        return " ".join(s.split()[::-1])

Futher discussion: We can not do better than O(n) space in python, because strings are immutable. However if we are given not string, but array of symbols, we can remove all extra spaces, using Two pointers approach, reverse full string and then reverse each word. Time complexity will be O(n) and space will be O(1).

Here is the python code:

  1. We traverse chars with two pointers and rewrite symbols in the beginning.
  2. Cut our chars, removing last elements (in my code it is not really inplace, but you can use del to do it in place)
  3. Reverse list using chars.reverse().
  4. Use two pointers to reverse each word.
class Solution:
    def reverseWords(self, s):       
        chars = [t for t in s]
        slow, n = 0, len(s)
        for fast in range(n):
            if chars[fast] != " " or (fast > 0 and chars[fast] == " " and chars[fast-1] != " "):
                chars[slow] = chars[fast]
                slow += 1
                
        if slow == 0: return ""       
        chars = chars[:slow-1] if chars[-1] == " " else chars[:slow]
        chars.reverse()
        
        slow, m = 0, len(chars)
        for fast in range(m + 1):
            if fast == m or chars[fast] == " ":
                chars[slow:fast] = chars[slow:fast][::-1]
                slow = fast + 1
                
        return "".join(chars)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0151