557. Reverse Words in a String III - Explanation

1. Convert To String Array

Intuition

The most straightforward approach splits the string into individual words, reverses each word separately, then joins them back together. By treating each word as an independent unit, we can use built-in string reversal methods on each one. This approach is simple to understand but requires extra space for the split words.

Algorithm

Split the input string by spaces to get an array of words.
For each word in the array, reverse its characters.
Join the reversed words back together with spaces between them.
Return the resulting string.

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

Time & Space Complexity

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

2. String Manipulation

Intuition

Instead of splitting into an array, we can build the result string character by character. As we scan through the input, we accumulate characters for each word in reverse order by prepending each new character. When we hit a space, we append the reversed word to our result and reset for the next word. This avoids explicit array operations but involves string concatenation.

Algorithm

Initialize an empty temporary string tmp_str and an empty result string res.
Iterate through each character in the input (plus one extra position to handle the last word).
If we reach a space or the end of the string:
- Append tmp_str to res, then clear tmp_str.
- If not at the end, append a space to res.
Otherwise, prepend the current character to tmp_str (building the word in reverse).
Return res.

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(n ^ 2)$
Space complexity: $O(n)$

3. Two Pointers - I

Intuition

We can reverse each word in place by identifying word boundaries and using two pointers to swap characters within each word. As we scan through the string, we track where each word starts. When we encounter a space or reach the end, we know the word boundaries and can reverse that segment. This approach modifies a character array copy of the string directly.

Algorithm

Convert the string to a character array.
Use pointer l to track the start of the current word.
Iterate with pointer r through the array:
- When r reaches a space or the end of the string, we have found a complete word.
- Use two temporary pointers to swap characters from both ends of this word toward the center.
- Update l to r + 1 for the next word.
Convert the character array back to a string and return.

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)$
Space complexity: $O(n)$

4. Two Pointers - II

Intuition

This is a cleaner variation of the two-pointer approach. Instead of checking for word boundaries at every position, we explicitly find each word by scanning for non-space characters. Once we locate a word's start, we scan to find its end, reverse the word in place, then jump to the next word. This makes the logic more explicit and easier to follow.

Algorithm

Convert the string to a character array.
Iterate through the array with index i:
- Skip spaces until finding a non-space character (start of a word).
- From that position, use index j to find where the word ends (next space or end of array).
- Call a helper function to reverse characters between indices i and j - 1.
- Move i to j to continue with the next word.
Return the modified array as a string.

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)$
Space complexity: $O(n)$

Common Pitfalls

Forgetting to Handle the Last Word

When iterating through the string looking for spaces to identify word boundaries, the last word has no trailing space. A common mistake is failing to reverse the final word because the loop only triggers reversal when encountering a space character.

Modifying Immutable Strings Directly

In languages where strings are immutable (like Python, Java, and JavaScript), attempting to modify the string in place will fail. You must first convert the string to a mutable data structure like a character array, perform the reversals, then convert back to a string.