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.
1using System;
2
3public class Solution {
4 public static string ReverseWords(string s) {
5 string[] words = s.Trim().Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries);
6 Array.Reverse(words);
7 return string.Join(" ", words);
8 }
9
10 public static void Main() {
11 string input = " hello world ";
12 string output = ReverseWords(input);
13 Console.WriteLine(output);
14 }
}In C#, the solution employs Trim() to handle spaces and Split() to handle empty substrings when splitting. The Array.Reverse() is used for reversing the split words before joining them with a space as the delimiter.
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.
1
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 Python solution focuses on reversing the entire string initially, followed by reversing every word back to its correct order. The final result is constructed by joining words effectively.