Reverse Words in a String

Problem#

Reverse the order of words in s. Words are sequences of non-space chars separated by one or more spaces. Strip leading/trailing spaces and collapse internal multi-spaces to single spaces.

Examples#

"the sky is blue" → "blue is sky the"
" hello world " → "world hello"
"a good example" → "example good a"

Constraints#

1 <= s.length <= 10^4, ASCII letters/digits/spaces, at least one word.

Hints#

Hint 1

Reverse the whole string, then reverse each word in place.

Hint 2

A write-pointer compacts the spaces in a second linear pass.

Approach#

Two-stage in-place: (1) trim and collapse spaces using a write pointer; (2) reverse the whole string, then reverse each word individually. Net result: words appear in reverse order with single-space separation.

Solution#

class Solution {
public:
    string reverseWords(string s) {
        // 1) compact: trim + collapse internal spaces
        int w = 0, i = 0, n = s.size();
        while (i < n) {
            while (i < n && s[i] == ' ') ++i;
            if (i == n) break;
            if (w > 0) s[w++] = ' ';
            while (i < n && s[i] != ' ') s[w++] = s[i++];
        }
        s.resize(w);
        // 2) reverse all, then reverse each word
        reverse(s.begin(), s.end());
        int start = 0;
        for (int j = 0; j <= (int)s.size(); ++j) {
            if (j == (int)s.size() || s[j] == ' ') {
                reverse(s.begin() + start, s.begin() + j);
                start = j + 1;
            }
        }
        return s;
    }
};

func reverseWords(s string) string {
    b := []byte(s)
    n := len(b)
    w, i := 0, 0
    for i < n {
        for i < n && b[i] == ' ' {
            i++
        }
        if i == n {
            break
        }
        if w > 0 {
            b[w] = ' '
            w++
        }
        for i < n && b[i] != ' ' {
            b[w] = b[i]
            w++
            i++
        }
    }
    b = b[:w]
    rev := func(lo, hi int) {
        for lo < hi {
            b[lo], b[hi] = b[hi], b[lo]
            lo++
            hi--
        }
    }
    rev(0, len(b)-1)
    start := 0
    for j := 0; j <= len(b); j++ {
        if j == len(b) || b[j] == ' ' {
            rev(start, j-1)
            start = j + 1
        }
    }
    return string(b)
}

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(reversed(s.split()))

function reverseWords(s) {
    return s.trim().split(/\s+/).reverse().join(' ');
}

class Solution {
    public String reverseWords(String s) {
        String[] parts = s.trim().split("\\s+");
        StringBuilder sb = new StringBuilder();
        for (int i = parts.length - 1; i >= 0; i--) {
            sb.append(parts[i]);
            if (i > 0) sb.append(' ');
        }
        return sb.toString();
    }
}

function reverseWords(s: string): string {
    return s.trim().split(/\s+/).reverse().join(' ');
}

Editorial#

The trick is decoupling “rearrange words” from “normalize whitespace”. Doing them in one pass tangles the indices; doing whitespace normalization first means the second stage operates on a clean canonical form, and “reverse all then re-reverse each word” is the canonical idiom for in-place word-order reversal — both operations are O(n) and need no extra buffer.

Complexity#

Time: O(n).
Space: O(1) extra (output reuses the input string).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#