557. Reverse Words in a String III - Explanation

Problem Link



1. Convert To String Array

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join([w[::-1] for w in s.split(' ')])

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

2. String Manipulation

class Solution:
    def reverseWords(self, s: str) -> str:
        tmp_str = ""
        res = ""

        for r in range(len(s) + 1):
            if r == len(s) or s[r] == ' ':
                res += tmp_str
                tmp_str = ""
                if r != len(s):
                    res += " "
            else:
                tmp_str = s[r] + tmp_str
        return res

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n)

3. Two Pointers - I

class Solution:
    def reverseWords(self, s: str) -> str:
        s = list(s)
        l = 0
        for r in range(len(s)):
            if s[r] == " " or r == len(s) - 1:
                temp_l, temp_r = l, r - 1 if s[r] == " " else r
                while temp_l < temp_r:
                    s[temp_l], s[temp_r] = s[temp_r], s[temp_l]
                    temp_l += 1
                    temp_r -= 1
                l = r + 1
        return "".join(s)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

4. Two Pointers - II

class Solution:
    def reverseWords(self, s: str) -> str:
        def reverse(i, j):
            while i < j:
                s[i], s[j] = s[j], s[i]
                i += 1
                j -= 1

        s = list(s)
        i = 0
        while i < len(s):
            if s[i] != ' ':
                j = i
                while j < len(s) and s[j] != ' ':
                    j += 1
                reverse(i, j - 1)
                i = j + 1
        return ''.join(s)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)