Reverse Words in a String
Reverse Words in a String is a medium arrays & hashing problem solved with the double reversal trick pattern.
The best approach, optimal (double reversal on a char array), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, from brute force (split and join) up.
Problem
Given a string s, return its words in reverse order, joined by a single space. A word is a run of non-space characters. The result must have no leading, trailing or repeated spaces.
Examples
Example 1
- Input
s = " dry run first "- Output
"first run dry"- Why
- Leading, trailing and repeated spaces are removed.
Example 2
- Input
s = "hello"- Output
"hello"
Constraints
1 <= s.length <= 10^4- s has letters, digits and spaces, with at least one word.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Brute force (split and join) | O(n) | O(n) |
| Optimal (double reversal on a char array) | O(n) | O(n) |
1Brute force (split and join)
O(n)O(n)Split on runs of whitespace, reverse the list of words and join with single spaces.
- Trim, then split on one or more spaces.
- Join the words from last to first.
class Solution {
public String reverseWords(String s) {
String[] words = s.trim().split("\\s+");
StringBuilder sb = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
sb.append(words[i]);
if (i > 0) sb.append(' ');
}
return sb.toString();
}
}2Optimal (double reversal on a char array)
O(n)O(n)Java strings are immutable, so one char array is needed. In a language with mutable strings this is O(1).Compact the string into a char array with single spaces, reverse the whole array, then reverse each word in place. This is the same trick as rotating an array and needs no word list.
- Copy characters, keeping only one space between words and none at the ends.
- Reverse the whole compacted range.
- Walk through it and reverse each word back.
class Solution {
public String reverseWords(String s) {
char[] a = s.toCharArray();
int n = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] == ' ') continue;
if (n > 0) a[n++] = ' ';
while (i < a.length && a[i] != ' ') a[n++] = a[i++];
}
reverse(a, 0, n - 1);
for (int i = 0; i < n; ) {
int j = i;
while (j < n && a[j] != ' ') j++;
reverse(a, i, j - 1);
i = j + 1;
}
return new String(a, 0, n);
}
private void reverse(char[] a, int i, int j) {
while (i < j) {
char t = a[i]; a[i] = a[j]; a[j] = t;
i++; j--;
}
}
}Edge cases to test
- Multiple spaces between words
- Leading or trailing spaces
- A single word
Hints
Hint 1
Reverse the whole string, then reverse each word back.
FAQ
What is the best time complexity for Reverse Words in a String?
Optimal (double reversal on a char array) runs in O(n) time and O(n) extra space.
Which pattern does Reverse Words in a String use?
It is a arrays & hashing problem that uses the double reversal trick pattern. Other problems with the same pattern: Rotate Array.
Is there a brute force solution for Reverse Words in a String?
Yes. Brute force (split and join) takes O(n) time and O(n) space. Split on runs of whitespace, reverse the list of words and join with single spaces.
Which edge cases should I test for Reverse Words in a String?
Multiple spaces between words; Leading or trailing spaces; A single word.