20 · String Parsing & Expression Evaluation
#151 Reverse Words in a String
frequently reported atAppleMicrosoftBloombergAmazonGoogleMeta
the problem
In plain words
A string s holds words made of letters and digits, separated by spaces. There may be extra spaces at the start, at the end, or between words. Return the words in reverse order, joined by exactly one space, with no spaces at either end.
in s = "the sky is blue"
out "blue is sky the"
in s = " hello world "
out "world hello"
The spaces at both ends disappear.
in s = "a good example"
out "example good a"
The run of three spaces becomes one.
- 1 ≤ s.length ≤ 10⁴
- s has English letters, digits and ' '
- s contains at least one word
- Follow-up: if strings could change in place, use O(1) extra space
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTwo pointers (opposite ends)Two pointers (read / write)
where this runsThe same reverse-all-then-reverse-each-part trick rotates an array in place (Rotate Array).
Reversing the whole text puts the words in the right order but spells each one backwards. Reverse each word once more and you are done — after squeezing the spaces.
solutions
From brute force to optimal
Read the words in order and put each one in front of the answer so far.
- Split the trimmed text into words.
- result = word + " " + result for each word.
Each prepend copies the whole answer so far: with n/2 one-letter words that is about n²/4 character copies.
The words and the growing answer.
class Solution { public String reverseWords(String s) { String result = ""; for (String word : s.trim().split(" +")) { // Put each word in FRONT of what we have. Every + copies the whole result again. result = result.isEmpty() ? word : word + " " + result; } return result; }}Let the library do it: split on runs of spaces, reverse the list, join with one space.
- words = s.trim().split("\\s+").
- Collections.reverse(Arrays.asList(words)).
- String.join(" ", words).
Splitting, reversing and joining are each linear.
The array of words and the new String.
class Solution { public String reverseWords(String s) { // trim() first: a leading space would make split return an empty first word. List<String> words = Arrays.asList(s.trim().split("\\s+")); Collections.reverse(words); return String.join(" ", words); }}Squeeze the spaces with read/write pointers, reverse the whole array, then reverse every word back.
- a = s.toCharArray(); compact: copy each word left with one space between words; n = new length.
- reverse(a, 0, n − 1).
- For each word [start, end): reverse(a, start, end − 1).
- Return new String(a, 0, n).
Each character is copied at most once and swapped about twice.
Java Strings are immutable, so the char[] copy itself is O(n); everything else is a few indices.
class Solution { public String reverseWords(String s) { char[] a = s.toCharArray(); // a String can't change, so work on its chars int n = compact(a); // one space between words, none at the ends reverse(a, 0, n - 1); // the whole text backwards: "eulb si yks eht" for (int start = 0; start < n; ) { int end = start; while (end < n && a[end] != ' ') end++; reverse(a, start, end - 1); // each word forwards again start = end + 1; } return new String(a, 0, n); } /** Copies the words to the front, one space apart; returns the new length. */ private int compact(char[] a) { int read = 0, write = 0; while (read < a.length) { while (read < a.length && a[read] == ' ') read++; // skip a run of spaces if (read == a.length) break; if (write > 0) a[write++] = ' '; // one space before every word but the first while (read < a.length && a[read] != ' ') a[write++] = a[read++]; // copy the word } return write; } private void reverse(char[] a, int i, int j) { while (i < j) { char t = a[i]; a[i++] = a[j]; a[j--] = t; } }}Dry run
in the room
How to say it in the interview
talk track
- Clarify the space rules: trim both ends, exactly one space between words.
- Give split + reverse + join first and state O(n) time and space.
- For the follow-up, explain reverse-all-then-each-word, and that Java needs a char[] copy because Strings can't change.
traps
s.split(" ")keeps empty strings for repeated spaces; uses.trim().split("\\s+").- Forgetting
trim(): a leading space makes split return an empty first word, which becomes a trailing space in the answer. - Building the answer with
+=in a loop: O(n²) copying.
what they ask next
Follow-ups
Reverse Words in a String II (LC 186): a char[] that already has single spaces?
Skip the compaction: reverse the whole array, then each word. O(n) time, O(1) space.
Reverse the letters of each word but keep the word order (LC 557)?
Only the last step: reverse each word in place.
before you submit
Edge cases to test
- Spaces at only one end: " x" → "x".
- A single word comes back unchanged.
- Several spaces between words collapse to one.
practise next
Similar problems
- #189Rotate ArrayMediumin Arrays & Strings
- #344Reverse StringEasyin Recursion
- #125Valid PalindromeEasyin Two Pointers