Problem Statement:
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.
Examples:
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 <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Approach
-
Trim the string → First, remove all leading and trailing
spacesfrom the given string to avoid unnecessary empty words at the beginning or end. -
Initialize variables → Create an empty
resultarray (or list) to store words in reverse order and a temporarywordstring to build characters. -
Traversethe string character by character → Iterate through each character of the string from left to right. -
Build each word →
- If the current character is not a
space, keep adding it to thewordvariable.
- If the current character is not a
-
When a
space is found:- Check if the current
wordis not empty. - If not empty, insert (push) the word at the front of the result to maintain reverse order.
Resetthewordto an empty string to start building the next word.
- Check if the current
-
Handle the last word → After the loop ends, check if a word is still present in the
wordvariable and add it to the front of the result. -
Join words → Finally, combine all words in the result using a
single spaceto form the reversed sentence.
Dry Run
Input: s = " hello world "
Step 1: Trim the string
s = s.trim()
→ s = "hello world"
Initial:
wordArray = []
word = ""
Step 2: c = 'h'
c !== " " → word += 'h'
word = "h"
Step 3: c = 'e'
word = "he"
Step 4: c = 'l'
word = "hel"
Step 5: c = 'l'
word = "hell"
Step 6: c = 'o'
word = "hello"
Step 7: c = ' '
c == " " and word.length > 0
→ wordArray.unshift("hello")
→ wordArray = ["hello"]
→ word = ""
Step 8: c = 'w'
word = "w"
Step 9: c = 'o'
word = "wo"
Step 10: c = 'r'
word = "wor"
Step 11: c = 'l'
word = "worl"
Step 12: c = 'd'
word = "world"
After loop ends:
word = "world" (last word)
Step 13: Push last word
wordArray.unshift("world")
→ wordArray = ["world", "hello"]
Step 14: Join array
wordArray.join(" ")
→ "world hello"
Output: "world hello"
var reverseWords = function(s) {
s = s.trim();
let wordArray = [];
let word = "";
for (let c of s) {
if (c !== " ") {
word += c;
} else if (word.length > 0) {
wordArray.unshift(word);
word = "";
}
}
// push the last word
if (word.length > 0) {
wordArray.unshift(word);
}
return wordArray.join(" ");
};
// Second Approach for JavaScript
Note:
JavaScript makes string manipulation very concise and efficient because it
provides powerful built-in methods like trim(),
split(), reverse(), and join().
These allow us to solve the problem in just a few lines of code. In contrast,
languages like Java, C++, or C require more verbose implementations due to
fewer direct utilities or the need for manual handling of strings. However,
the core logic remains the same across all languages — clean the string,
split it into words, reverse the order, and join them back together.
s = s.trim();
let words = s.split(/\s+/);
return words.reverse().join(" ");
};
def reverseWords(s: str) -> str:
s = s.strip()
word_array = []
word = ""
for c in s:
if c != " ":
word += c
elif word:
word_array.insert(0, word)
word = ""
if word:
word_array.insert(0, word)
return " ".join(word_array)
class Solution {
public String reverseWords(String s) {
s = s.trim();
LinkedList wordArray = new LinkedList<>();
String word = "";
for (char c : s.toCharArray()) {
if (c != ' ') {
word += c;
} else if (word.length() > 0) {
wordArray.addFirst(word);
word = "";
}
}
if (word.length() > 0) {
wordArray.addFirst(word);
}
return String.join(" ", wordArray);
}
}
class Solution {
public:
string reverseWords(string s) {
vector wordArray;
string word = "";
// trim manually
int i = 0, j = s.size() - 1;
while (i <= j && s[i] == ' ') i++;
while (j >= i && s[j] == ' ') j--;
for (int k = i; k <= j; k++) {
if (s[k] != ' ') {
word += s[k];
} else if (!word.empty()) {
wordArray.insert(wordArray.begin(), word);
word = "";
}
}
if (!word.empty()) {
wordArray.insert(wordArray.begin(), word);
}
string result = "";
for (int i = 0; i < wordArray.size(); i++) {
result += wordArray[i];
if (i != wordArray.size() - 1) result += " ";
}
return result;
}
};
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* reverseWords(char* s) {
int n = strlen(s);
char** words = (char**)malloc(n * sizeof(char*));
int count = 0;
char word[1000];
int w = 0;
for (int i = 0; i <= n; i++) {
if (s[i] != ' ' && s[i] != '\0') {
word[w++] = s[i];
} else if (w > 0) {
word[w] = '\0';
words[count] = (char*)malloc((w + 1) * sizeof(char));
strcpy(words[count], word);
count++;
w = 0;
}
}
char* result = (char*)malloc(n + 1);
result[0] = '\0';
for (int i = count - 1; i >= 0; i--) {
strcat(result, words[i]);
if (i != 0) strcat(result, " ");
}
return result;
}
using System;
using System.Collections.Generic;
public class Solution {
public string ReverseWords(string s) {
s = s.Trim();
LinkedList wordArray = new LinkedList();
string word = "";
foreach (char c in s) {
if (c != ' ') {
word += c;
} else if (word.Length > 0) {
wordArray.AddFirst(word);
word = "";
}
}
if (word.Length > 0) {
wordArray.AddFirst(word);
}
return string.Join(" ", wordArray);
}
}
