In this problem “Reverse words in a String”, we are given an input string s. We need to reverse the order of the words and return a string of the words in reverse order.
Takeaways
In this article we will learn how to reverse words in a string using different approach.
Example
Input :
s = "welcome to scaler topics"
Output :
"topics scaler to welcome"
Example Explanation
The string given to us is “welcome to scaler topics”. To reverse the words of this string, we need to think of a logic to reverse the words and also to remove any leading or trailing spaces. This gives us “topics scaler to welcome”.
Constraints
- Length of the string s will be between 1 and 104.
- s could contain English letters (upper-case and lower-case), digits, and spaces ‘ ‘.
- There is at least one word in s.
Approach 1 : Splitting and Saving the String in a Reverse Manner
One of the easiest ways to reverse words in a string is by splitting the string and then saving it in reverse order. This is the naive approach. We will now look at the code for this method :
Java Implementation
In Java, we have the split method, which helps us split the string. We use it to split the string using the delimiter and reverse and store the line in another variable.
public class Scaler {
public static void main(String[] args) {
String input = "hello world";
String s[] = input.split(" ");
String res = "";
for (int i = s.length - 1; i >= 0; i--) {
res += s[i] + " ";
}
System.out.println(res.substring(0, res.length() - 1));
}
}
Output :
world hello
Python Implementation
In python too, we have the split method, which helps us split the string. We use it to split the string using the delimiter and reverse and store the line in another variable.
s = "hello world"
words = s.split(' ')
res =[]
for word in words:
res.insert(0, word)
print(" ".join(res))
Output :
world hello
C++ Implementation
#include <iostream>
using namespace std;
string reverseWords(string s) {
string word = "";
string res = "";
for (char i: s) {
if (i == ' ') {
res = word + " " + res;
word = "";
} else {
word += i;
}
}
res = word + " " + res;
return res.substr(0, res.size() - 1);
}
int main() {
string input = "hello world";
string res = reverseWords(input);
cout << res;
return 0;
}
Output :
world hello
Complexity Analysis
Let’s analyze the time and space complexity of this approach :
Time Complexity : O(n) as we use only one for a loop.
Space Complexity : O(n) as we are storing our output that is, the reversed string in a new variable.
Approach 2 : Using the Two-Pointers Approach
Now, here comes the optimal solution for this problem.
We initialize two pointers, one at the start of the string and another at the end. Then, we swap the words from the start and end, to achieve the reversed string.
Algorithm :
- Turn the string s into an array of strings in which the words of s are stored.
- Now, initialise the left and right pointers at 0 and s.length() – 1.
- Now, we need to swap the elements at the left and right pointers. For that, move the left pointer ahead and the right pointer backward by one position and swap the elements at each position while the left pointer does not exceed the right pointer.
- Return the final string.
Java Implementation
import java.util.*;
public class Scaler {
public static String Reverse(String[] words) {
int left = 0, right = words.length - 1;
while (left <= right) {
String temp = words[left];
words[left] = words[right];
words[right] = temp;
left += 1;
right -= 1;
}
String res = String.join(" ", words);
return res;
}
public static void main(String[] args) {
String s = "welcome reader";
String[] words = s.split("\\s").trim();
String res = Reverse(words);
System.out.println(res);
}
}
Output :
reader welcome
Python Implementation
s = "welcome reader"
s = s.split(" ")
left = 0
right = len(s) - 1
while left <= right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
res = " ".join(s)
print(res)
Output :
reader welcome
C++ Implementation
#include <iostream>
#include <vector>
using namespace std;
string reverseWords(string s) {
vector < string > words;
string str = "";
for (char c: s) {
if (c == ' ') {
words.push_back(str);
str = "";
} else {
str += c;
}
}
words.push_back(str);
int left = 0, right = words.size() - 1;
while (left <= right) {
swap(words[left], words[right]);
left++;
right--;
}
string res = "";
for (auto x: words) {
res += x;
res += " ";
}
res.pop_back();
return res;
}
int main() {
string input = "hello world";
string res = reverseWords(input);
cout << res;
return 0;
}
Output :
world hello
Complexity Analysis
Let’s analyze the time and space complexity of this approach :
Time Complexity : O(n)
Space Complexity : O(1)
Conclusion
- Reverse words in a string is a really important problem regarding interview preparation.
- One of the easiest ways to solve this problem is by splitting the string and then saving it in reverse order.
- Another way is to swap the words from the start and end to achieve the reversed string. This is also the optimal solution to the problem.
