151.Reverse-Words-in-a-String.md

151. Reverse Words in a String

Difficulty: Medium

URL

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

Solution

Approach 1: Naive Approach

Divide the problem into two subproblems and make sure the size of the problem reduce each time we make a recursive call.

The run time for this approach is $O(n)$.

The code is shown below:

class Solution:
    def reverseWords(self, s: str) -> str:
        # removing leading and tailing white space
        s = s.strip().split()
        left = 0
        right = len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
        return " ".join(s)