Reverse Words in a String III
Reverse Words in a String III is a easy arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (two pointers on a character array), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (split, reverse, join) up.
Problem
Given a sentence s, reverse the order of the characters inside every word while keeping the words themselves, and the single spaces between them, in their original order.
A word is a maximal run of non-space characters. Return the resulting string.
Examples
Example 1
- Input
s = "code every morning"- Output
"edoc yreve gninrom"- Why
- Each word is reversed on its own; the words stay in the same order.
Example 2
- Input
s = "Go 2 it!"- Output
"oG 2 !ti"- Why
- Digits and punctuation are ordinary characters of their word.
Example 3
- Input
s = "a"- Output
"a"- Why
- A single one-letter word is unchanged.
Constraints
1 <= s.length <= 5 * 10^4scontains printable ASCII characters.- There are no leading or trailing spaces, and words are separated by exactly one space.
- There is at least one word.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (split, reverse, join) | O(n) | O(n) |
| Optimal (two pointers on a character array) | O(n) | O(n) |
1Brute force (split, reverse, join)
O(n)Every character is copied a constant number of times.O(n)The word array, the reversed copies and the joined result.Split the string on spaces, reverse every word into a new string, and join the reversed words back with single spaces.
- Split
son ' ' into words. - For each word, build its reverse.
- Join the reversed words with ' '.
class Solution {
public String reverseWords(String s) {
String[] words = s.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < words.length; i++) {
if (i > 0) sb.append(' ');
sb.append(new StringBuilder(words[i]).reverse());
}
return sb.toString();
}
}class Solution:
def reverseWords(self, s: str) -> str:
words = s.split(" ")
return " ".join(w[::-1] for w in words)class Solution {
public:
string reverseWords(string s) {
vector<string> words;
string cur;
for (char c : s) {
if (c == ' ') {
words.push_back(cur);
cur.clear();
} else {
cur.push_back(c);
}
}
words.push_back(cur);
string out;
for (size_t i = 0; i < words.size(); i++) {
if (i > 0) out.push_back(' ');
out += string(words[i].rbegin(), words[i].rend());
}
return out;
}
};function reverseWords(s) {
return s.split(" ").map((w) => w.split("").reverse().join("")).join(" ");
}2Optimal (two pointers on a character array)
O(n)Each character is visited once by the scan and swapped at most once.O(n)The char array (strings are immutable); no other buffers.Copy the string into a character array once. Scan for each word's boundaries, and reverse the characters between them in place by swapping from both ends toward the middle. Spaces never move.
- Convert
sto a char arrayc. - Let start = 0. For i from 0 to n: when i == n or
c[i] == ' ', reversec[start..i-1]and set start = i + 1. - Reverse: swap
c[l]andc[r], then l++, r-- while l < r. - Return the array as a string.
class Solution {
public String reverseWords(String s) {
char[] c = s.toCharArray();
int n = c.length, start = 0;
for (int i = 0; i <= n; i++) {
if (i == n || c[i] == ' ') {
int l = start, r = i - 1;
while (l < r) {
char t = c[l];
c[l++] = c[r];
c[r--] = t;
}
start = i + 1;
}
}
return new String(c);
}
}class Solution:
def reverseWords(self, s: str) -> str:
c = list(s)
n, start = len(c), 0
for i in range(n + 1):
if i == n or c[i] == ' ':
l, r = start, i - 1
while l < r:
c[l], c[r] = c[r], c[l]
l += 1
r -= 1
start = i + 1
return "".join(c)class Solution {
public:
string reverseWords(string s) {
int n = s.size(), start = 0;
for (int i = 0; i <= n; i++) {
if (i == n || s[i] == ' ') {
int l = start, r = i - 1;
while (l < r) swap(s[l++], s[r--]);
start = i + 1;
}
}
return s;
}
};function reverseWords(s) {
const c = s.split("");
const n = c.length;
let start = 0;
for (let i = 0; i <= n; i++) {
if (i === n || c[i] === ' ') {
let l = start, r = i - 1;
while (l < r) {
const t = c[l];
c[l++] = c[r];
c[r--] = t;
}
start = i + 1;
}
}
return c.join("");
}Edge cases to test
- A single word
- One-character words
- Palindromic words that look unchanged
Hints
Hint 1
Find where each word starts and ends: it ends right before a space or at the end of the string.
Hint 2
Reverse each word in place with two pointers swapping from both ends.
FAQ
What is the best time complexity for Reverse Words in a String III?
Optimal (two pointers on a character array) runs in O(n) time and O(n) extra space. Each character is visited once by the scan and swapped at most once.
Which pattern does Reverse Words in a String III use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Reverse Words in a String III?
Yes. Brute force (split, reverse, join) takes O(n) time and O(n) space. Split the string on spaces, reverse every word into a new string, and join the reversed words back with single spaces.
Which edge cases should I test for Reverse Words in a String III?
A single word; One-character words; Palindromic words that look unchanged.