Given an input string, containing upper-case and lower-case letters, digits, and spaces( ' ' ). A word is defined as a sequence of non-space characters. The words in s are separated by at least one space.
Return a string with the words in reverse order, concatenated by a single space.
Input: s = "welcome to the jungle"
Output: "jungle the to welcome"
Explanation: The words in the input string are "welcome", "to", "the", and "jungle". Reversing the order of these words gives "jungle", "the", "to", and "welcome". The output string should have exactly one space between each word.
Input: s = " amazing coding skills "
Output: "skills coding amazing"
Explanation: The input string has leading and trailing spaces, as well as multiple spaces between the words "amazing", "coding", and "skills". After trimming the leading and trailing spaces and reducing the multiple spaces between words to a single space, the words are "amazing", "coding", and "skills". Reversing the order of these words gives "skills", "coding", and "amazing". The output string should not have any leading or trailing spaces and should have exactly one space between each word.
Input: s = "openAI is innovative"
A brute force way to solve the problem will be to extract every word from the given string. Once all the words are extracted, the resulting string can be formed by adding all the words in the reverse order keeping a space in betweeen.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to reverse every word in the given string
string reverseWords(string s) {
int n = s.length(); // Length of string
// List to store the words present in string
vector<string> words;
// Pointers to mark the start and end of a word
int start, end;
int i = 0;
while(i < n) {
// Finding the first character of a word (if any)
while(i < n && s[i] == ' ') i++;
// If no word is found, break
if(i >= n) break;
start = i; // Storing the index of first character of word
// Finding the last character of the word
while(i < n && s[i] != ' ') i++;
end = i-1; // Storing the index of last character of word
// Add the found word to the list of words
string wordFound = s.substr(start, end-start+1);
words.push_back(wordFound);
}
string ans = "";
// Adding all the words to result in the reverse order
for(int i = words.size() - 1; i >= 0; i--) {
ans += words[i];
// Adding spaces in between words
if(i != 0) ans.push_back(' ');
}
return ans; // Return the stored result
}
};
int main(){
string s = " amazing coding skills ";
// Creating an instance of Solution class
Solution sol;
// Function call to reverse every word in the given string
string ans = sol.reverseWords(s);
// Output
cout << "Input string: " << s << endl;
cout << "After reversing every word: " << ans << endl;
}import java.util.*;
class Solution {
// Function to reverse every word in the given string
public String reverseWords(String s) {
int n = s.length(); // Length of string
// List to store the words present in string
List<String> words = new ArrayList<>();
// Pointers to mark the start and end of a word
int start, end;
int i = 0;
while (i < n) {
// Finding the first character of a word (if any)
while (i < n && s.charAt(i) == ' ') i++;
// If no word is found, break
if (i >= n) break;
start = i; // Storing the index of first character of word
// Finding the last character of the word
while (i < n && s.charAt(i) != ' ') i++;
end = i - 1; // Storing the index of last character of word
// Add the found word to the list of words
String wordFound = s.substring(start, end + 1);
words.add(wordFound);
}
StringBuilder ans = new StringBuilder();
// Adding all the words to result in the reverse order
for (int j = words.size() - 1; j >= 0; j--) {
ans.append(words.get(j));
// Adding spaces in between words
if (j != 0) ans.append(' ');
}
return ans.toString(); // Return the stored result
}
}
class Main {
public static void main(String[] args) {
String s = " amazing coding skills ";
// Creating an instance of Solution class
Solution sol = new Solution();
// Function call to reverse every word in the given string
String ans = sol.reverseWords(s);
// Output
System.out.println("Input string: " + s);
System.out.println("After reversing every word: " + ans);
}
}class Solution:
# Function to reverse every word in the given string
def reverseWords(self, s: str) -> str:
n = len(s) # Length of string
# List to store the words present in string
words = []
# Pointers to mark the start and end of a word
start = end = 0
i = 0
while i < n:
# Finding the first character of a word (if any)
while i < n and s[i] == ' ':
i += 1
# If no word is found, break
if i >= n:
break
start = i # Storing the index of first character of word
# Finding the last character of the word
while i < n and s[i] != ' ':
i += 1
end = i - 1 # Storing the index of last character of word
# Add the found word to the list of words
wordFound = s[start:end + 1]
words.append(wordFound)
ans = ""
# Adding all the words to result in the reverse order
for i in range(len(words) - 1, -1, -1):
ans += words[i]
# Adding spaces in between words
if i != 0:
ans += ' '
return ans # Return the stored result
if __name__ == "__main__":
s = " amazing coding skills "
# Creating an instance of Solution class
sol = Solution()
# Function call to reverse every word in the given string
ans = sol.reverseWords(s)
# Output
print("Input string:", s)
print("After reversing every word:", ans)class Solution {
// Function to reverse every word in the given string
reverseWords(s) {
let n = s.length; // Length of string
// List to store the words present in string
let words = [];
// Pointers to mark the start and end of a word
let start, end;
let i = 0;
while (i < n) {
// Finding the first character of a word (if any)
while (i < n && s[i] === ' ') i++;
// If no word is found, break
if (i >= n) break;
start = i; // Storing the index of first character of word
// Finding the last character of the word
while (i < n && s[i] !== ' ') i++;
end = i - 1; // Storing the index of last character of word
// Add the found word to the list of words
let wordFound = s.slice(start, end + 1);
words.push(wordFound);
}
let ans = "";
// Adding all the words to result in the reverse order
for (let i = words.length - 1; i >= 0; i--) {
ans += words[i];
// Adding spaces in between words
if (i !== 0) ans += ' ';
}
return ans; // Return the stored result
}
}
// Main block
const s = " amazing coding skills ";
// Creating an instance of Solution class
const sol = new Solution();
// Function call to reverse every word in the given string
const ans = sol.reverseWords(s);
// Output
console.log("Input string:", s);
console.log("After reversing every word:", ans);
Time Complexity: O(n) (where n is the length of the input string)
The brute force approach used an additional list to store the words found in the string.
An optimal approach can be to reverse the words in-place. For this, the whole string is reversed in-place making each word's characters reversed. Now, each word is identified and its characters are reversed again to restore the correct character order within each word.
Extra spaces are moved to the end by shifting each word with the appropriate spacing.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Helper function to reverse the string
void reverseString(string &s, int start, int end) {
// Reversing the string character by character
while(start < end) {
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start++, end--;
}
return;
}
public:
// Function to reverse every word in the given string
string reverseWords(string s) {
int n = s.length(); // Length of string
// Reverse the complete string
reverseString(s, 0, n-1);
int start = 0, end = 0;
int i = 0, j = 0;
while(j < n) {
// Skip any white spaces
while(j < n && s[j] == ' ') j++;
start = i; // Store the start of the word
// Until the word ends
while(j < n && s[j] != ' ') {
s[i] = s[j]; // Shift the characters
i++, j++;
}
end = i-1; // Store the end of the word
// Reverse the word found
reverseString(s, start, end);
// Adding a space after every word
s[i++] = ' ';
}
// Return the result containing all words
string ans = s.substr(0, end+1);
return ans;
}
};
int main(){
string s = " amazing coding skills ";
// Creating an instance of Solution class
Solution sol;
// Function call to reverse every word in the given string
string ans = sol.reverseWords(s);
// Output
cout << "Input string: " << s << endl;
cout << "After reversing every word: " << ans << endl;
}import java.util.*;
class Solution {
// Helper function to reverse the string
private void reverseString(char[] s, int start, int end) {
// Reversing the string character by character
while(start < end) {
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
// Function to reverse every word in the given string
public String reverseWords(String s) {
// Converting string to array because strings are immutable in Java
char[] arr = s.toCharArray();
int n = arr.length; // Length of array
// Reverse the complete string
reverseString(arr, 0, n-1);
int start = 0, end = 0;
int i = 0, j = 0;
while(j < n) {
// Skip any white spaces
while(j < n && arr[j] == ' ') j++;
start = i; // Store the start of the word
// Until the word ends
while(j < n && arr[j] != ' ') {
arr[i] = arr[j]; // Shift the characters
i++;
j++;
}
end = i-1; // Store the end of the word
// Reverse the word found
reverseString(arr, start, end);
// Adding a space after every word
if(i < n) arr[i++] = ' ';
}
// Return the result containing all words
return new String(arr).substring(0, end + 1); // Using substring for slicing
}
}
class Main {
public static void main(String[] args) {
String s = "welcome to the jungle";
// Creating an instance of Solution class
Solution sol = new Solution();
// Function call to reverse every word in the given string
String ans = sol.reverseWords(s);
// Output
System.out.println("Input string: " + s);
System.out.println("After reversing every word: " + ans);
}
}class Solution:
# Helper function to reverse the string
def reverseString(self, s, start, end):
# Reversing the string character by character
while start < end:
s[start], s[end] = s[end], s[start]
start, end = start + 1, end - 1
# Function to reverse every word in the given string
def reverseWords(self, s):
s = list(s) # Convert to list to allow modification
n = len(s) # Length of string
# Reverse the complete string
self.reverseString(s, 0, n - 1)
start = 0
end = 0
i = 0
j = 0
while j < n:
# Skip any white spaces
while j < n and s[j] == ' ':
j += 1
start = i # Store the start of the word
# Until the word ends
while j < n and s[j] != ' ':
s[i] = s[j] # Shift the characters
i += 1
j += 1
end = i - 1 # Store the end of the word
# Reverse the word found
self.reverseString(s, start, end)
# Adding a space after every word
if i < n:
s[i] = ' '
i += 1
# Return the result containing all words
return ''.join(s[:end + 1])
# Creating an instance of Solution class
sol = Solution()
# Function call to reverse every word in the given string
s = " amazing coding skills "
ans = sol.reverseWords(s)
# Output
print("Input string:", s)
print("After reversing every word:", ans)class Solution {
// Helper function to reverse the string
reverseString(s, start, end) {
// Reversing the string character by character
while(start < end) {
let temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
// Function to reverse every word in the given string
reverseWords(s) {
let arr = s.split(''); // Convert to array to allow modification
let n = arr.length; // Length of string
// Reverse the complete string
this.reverseString(arr, 0, n-1);
let start = 0, end = 0;
let i = 0, j = 0;
while(j < n) {
// Skip any white spaces
while(j < n && arr[j] === ' ') j++;
start = i; // Store the start of the word
// Until the word ends
while(j < n && arr[j] !== ' ') {
arr[i] = arr[j]; // Shift the characters
i++;
j++;
}
end = i-1; // Store the end of the word
// Reverse the word found
this.reverseString(arr, start, end);
// Adding a space after every word
arr[i++] = ' ';
}
// Return the result containing all words
return arr.slice(0, end + 1).join('');
}
}
// Creating an instance of Solution class
const sol = new Solution();
let s = " amazing coding skills ";
// Function call to reverse every word in the given string
let ans = sol.reverseWords(s);
// Output
console.log("Input string:", s);
console.log("After reversing every word:", ans);
Time Complexity: O(n) (where n is the length of the input string)
Q: Why do we need to handle multiple spaces separately?
A: Spaces between words can be irregular, and using split() ensures that extra spaces are ignored when reversing.
Q: Can we solve this in-place without extra space?
A: Yes, but it requires modifying the string by: Reversing the entire string. Reversing individual words while maintaining correct spacing. This approach is useful for low-memory constraints.
Q: How would you modify this solution to reverse only words of even length?
A: Instead of reversing the entire word sequence, iterate and selectively reverse only even-length words before concatenation.
Q: What if we need to reverse the words in groups of k instead of completely?
A: The problem can be modified to group every k words and reverse within each group, similar to reversing k nodes in a linked list.