LeetCode 151. Reverse Words in a String

Intuition

Use sliding window to append words from the end to beginning in correct order

1. initialize res and right pointer
2. start from back and find end of the word using while r greater than equal to 0 and s[r] == ' '
3. when beginning of word is found initialize l pointer by using while s[l] != " "
4. append to result array window between l and r
5. move right pointer to l which is the beginning of the word
6. Repeat

Optimal Solution

class Solution:
	def reverseWords(self, s: str) -> str:
		res = []
		s = s.strip()
		
		while r >= 0:
			# skip spaces
			while r  >= 0 and s[r] == ' ':
				r -= 1
				
			# find beginning of the word
			l = r
			while l >= 0 and s[l] != ' ':
				l -=1
				
			# extract the word and add to result
			if r >= 0:
				res.append(s[l + 1 : r + 1])
			
			# move the right pointer to the left pointer
			r = l
		return " ".join(res)

Time Complexity

Time Complexity = O(N)

Space Complexity = O(N)