Reverse Words in a String III

How it works

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.

Steps

1. Convert the string to a character array.
2. 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.
3. Return the modified array as a string.

Complexity

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

Things to watch for

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.

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
            i += 1
        return ''.join(s)

class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s[i] != ' ') {
                int j = i;
                while (j < n && s[j] != ' ') {
                    j++;
                }
                reverse(s, i, j - 1);
                i = j;
            }
        }
        return s;
    }

private:
    void reverse(string& s, int i, int j) {
        while (i < j) {
            swap(s[i], s[j]);
            i++;
            j--;
        }
    }
};