Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = "the sky is blue" Output: "blue is sky the"
Example 2:
Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Constraints:
1 <= s.length <= 104s contains English letters (upper-case and lower-case), digits, and spaces ' '.s.Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
In #151 Reverse Words in a String, the goal is to reverse the order of words while removing extra spaces. A word is defined as a sequence of non-space characters, and the final string should contain words separated by a single space.
A common and efficient idea is to use a two-pointer strategy combined with string manipulation. First, remove leading, trailing, and extra intermediate spaces. Then reverse the entire string. After that, iterate through the string and reverse each individual word using two pointers. This restores the correct character order while keeping the word order reversed.
Another intuitive approach is to split the string into words, ignore empty tokens, and rebuild the sentence in reverse order using a list or stack-like structure.
The optimal implementations run in O(n) time since each character is processed a constant number of times. Space complexity can be O(1) for in-place manipulation or O(n) if auxiliary structures like arrays or stacks are used.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Reverse Entire String + Reverse Each Word (Two Pointers) | O(n) | O(1) |
| Split Words and Rebuild in Reverse Order | O(n) | O(n) |
Knowledge Center
This approach involves splitting the original string into individual words using space as a delimiter, reversing the list of words, and then joining them back together with a single space.
Time Complexity: O(N), where N is the length of the string, as we process each character once.
Space Complexity: O(N), additional space for intermediate and result storage.
1#include <iostream>
2#include <sstream>
3#include <vector>
4#include <algorithm>
5
6std::string reverseWords(std::string s) {
7 std::stringstream ss(s);
8 std::string word;
9 std::vector<std::string> words;
10
11 while (ss >> word) {
12 words.push_back(word);
13 }
14 std::reverse(words.begin(), words.end());
std::string result;
for (const std::string& w : words) {
if (!result.empty()) {
result += " ";
}
result += w;
}
return result;
}
int main() {
std::string input = " hello world ";
std::string output = reverseWords(input);
std::cout << output << std::endl;
return 0;
}This C++ solution utilizes the stringstream to extract words and stores them in a vector. It then reverses the vector and constructs the result string by iterating through the reversed vector.
This optimized approach manipulates the string in place by using a character array. We'll first reverse the entire string, and then reverse each word to return them to their correct order.
Time Complexity: O(N), where N is the number of characters in the string.
Space Complexity: O(1), as the operation is done in-place without extra space.
1using System.Text;
public class Solution {
public static string ReverseWords(string s) {
char[] chars = s.Trim().ToCharArray();
int n = chars.Length;
void Reverse(int start, int end) {
while (start < end) {
char temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;
start++;
end--;
}
}
Reverse(0, n - 1);
int rightIndex = 0;
for (int i = 0; i < n; ++i) {
if (chars[i] == ' ') continue;
int start = i;
while (i < n && chars[i] != ' ') i++;
Reverse(start, i - 1);
while (start < i) chars[rightIndex++] = chars[start++];
if (rightIndex < n) chars[rightIndex++] = ' ';
}
return new String(chars, 0, rightIndex == 0 ? 0 : rightIndex - 1);
}
public static void Main() {
string input = " hello world ";
string output = ReverseWords(input);
Console.WriteLine(output);
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations are commonly asked in technical interviews at companies like Amazon, Google, and Meta. It tests understanding of string manipulation, edge cases with spaces, and efficient in-place processing.
Two pointers are commonly used for the in-place solution because they allow efficient reversal of characters and words. Alternatively, arrays or stacks can be used after splitting the string into words, which simplifies implementation but uses extra space.
The optimal approach reverses the entire string first and then reverses each individual word using two pointers. This technique ensures that words appear in reversed order while maintaining correct character order. It runs in O(n) time and can be implemented with O(1) extra space.
You should remove leading and trailing spaces and ensure only a single space separates words. This can be done during preprocessing or while iterating through the string using pointers to skip multiple spaces.
The C# solution includes reversing the whole character array initially, and then processing each token to be reversed in place before constructing the final string with correct whitespace handling.