LeetCode — 151. Reverse Words in a String

Handling strings efficiently is a common challenge in programming. Today, we’ll discuss an elegant method to reverse the words in a string by first removing extra spaces and then applying a double reversal technique.

The Approach

Our solution involves two primary steps:

• Removing extra spaces from the string.
• Then reversing the entire string, followed by reversing each word individually.

1. Removing Extra Spaces

The key to this process lies in the removeExtraSpaces function. Here's how it works:

• Fast and Slow Pointer Technique: We use two pointers, fast and slow. The fast pointer scans through the string, while the slow pointer builds the new string without extra spaces.
• Handling Spaces: We ensure that no leading, trailing, or redundant middle spaces are included. When the fast pointer encounters a non-space character, and the slow pointer is not at the start, we add a single space to separate words.
• Building the New String: As the fast pointer moves, we copy each character to the position of the slow pointer, effectively removing unnecessary spaces.

2. Reversing the String

Once extra spaces are removed, we reverse the entire string:

• Full String Reversal: We reverse the entire string from start to end. This step makes each word within the string appear in the correct order but reversed.
• Word-by-Word Reversal: We then iterate through the string and reverse each word individually. This corrects the order of characters within each word.

Time and Space Complexity

• Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the string. Each character is processed a constant number of times.
• Space Complexity: The space complexity is O(n) for the new character array formed after removing extra spaces. The in-place modifications keep space usage minimal.

JavaScript version

/**
 * @param {string} s
 * @return {string}
 */
let removeExtraSpaces = function (sArr) {
    let slow = 0;
    // Use the fast and slow pointer to remove the beginning, end and the middle of
    // the redundant space
    for (let i = 0; i < sArr.length; ++i) {
        // fast pointer removes all the space
        if (sArr[i] !== ' ') {
            // slow pointer to add space between every words
            if (slow !== 0) sArr[slow++] = ' ';

            while (i < sArr.length && sArr[i] !== ' ') {
                sArr[slow++] = sArr[i++];
            }
        }
    }
    sArr.splice(slow, sArr.length-slow);
}

let reverseStr = function (sArr, start, end) {
    while (start < end) {
        [sArr[start], sArr[end]] = [sArr[end], sArr[start]];
        start++;
        end--;
    }
}

var reverseWords = function (s) {
    const sArr = s.split('');
    // remove all extra spaces
    removeExtraSpaces(sArr);
    // reversal the whole string
    reverseStr(sArr, 0, s.length - 1);

    let start = 0;
    for (let i = 0; i <= sArr.length; i++) {
        if (sArr[i] === ' ' || i === sArr.length) {
            reverseStr(sArr, start, i - 1);
            start = i + 1;
        }
    }
    return sArr.join('');
};

Java version

class Solution {
    public String reverseWords(String s) {
        char[] sArr = s.toCharArray();

        // remove all extra spaces
        sArr = removeExtraSpaces(sArr);
        // reversal the whole string
        reverseStr(sArr, 0, sArr.length - 1);

        int start = 0;
        for (int i = 0; i <= sArr.length; i++) {
            if (i == sArr.length || sArr[i] == ' ') {
                reverseStr(sArr, start, i - 1);
                start = i + 1;
            }
        }

        return new String(sArr);
    }

    public char[] removeExtraSpaces(char[] sArr) {
        int slow = 0;

        // Use the fast and slow pointer to remove the beginning, end and the middle of
        // the redundant space
        for (int fast = 0; fast < sArr.length; fast++) {
            // fast pointer removes all the space
            if (sArr[fast] != ' ') {
                // slow pointer to add space between every words
                if (slow != 0) {
                    sArr[slow] = ' ';
                    slow++;
                }

                while (fast < sArr.length && sArr[fast] != ' ') {
                    sArr[slow] = sArr[fast];
                    slow++;
                    fast++;
                }
            }
        }

        char[] newChars = new char[slow];
        System.arraycopy(sArr, 0, newChars, 0, slow);
        return newChars;
    }

    public void reverseStr(char[] sArr, int left, int right) {
        if (right >= sArr.length) {
            System.out.println("set a wrong right");
            return;
        }

        while (left < right) {
            sArr[left] ^= sArr[right];
            sArr[right] ^= sArr[left];
            sArr[left] ^= sArr[right];

            left++;
            right--;
        }
    }
}