Last Updated on October 3, 2022 by Ria Pathak
Problem Statment
You are given a string. This string contains many words that are space separated. You have to reverse each word in the string individually.
Examples
The input string is “Hello and Welcome to PrepBytes”.
So, the output for this string should be “olleH dna emocleW ot setyBperP”.
Let us take another example. Say the input string is “Hello”. So, the output for this is “olleH”. Since there is only one word, we reverse it. Please note that there is no space after the last word in both the outputs.
Constraints
The input string will only have 1 whitespace between the words. Also, for the output, you have to maintain the same.
It is recommended not to use any predefined functions for reversing the strings to solve the problem.
Basic Approach
The primary approach is to get all the words in an ArrayList or vector of strings. Then, we can reverse each word and print them space-separated. This is shown below.
The input string is as shown. We have a pointer at the first index of the input string. Since it is a character and not a whitespace, the pointer keeps moving forward and we keep adding the characters to a temporary string till the pointer encounters whitespace.
As space is encountered, we insert the temporary string in our vector/ArrayList. So, the same will happen for the next word as shown below.
Now, the last word will not encounter a string. So, when the pointer reaches index = size of the input string, we will insert the last string into the vector/ArrayList.
Now that we have all the words with us, we reverse each word and add them with a space into the output string.
When we insert the last word, we will not insert space after it.
Now, we only need to learn to reverse a string. So, let us discuss it.
Reverse a Word
Consider the word shown below
We have taken 2 pointers, low and high. The pointer low is at the index 0 and the pointer high is at the last index of the word.
We will swap the characters at low and high and increment the low pointer and decrement the high pointer till low is less than high. This will reverse the word as shown below.
Note: In Java, we will use StringBuilder (or StringBuffer) in place of Strings as Strings are immutable in Java, and reversing a String is an O(N2) operation in Java (since the same string does not get reversed and a new copy is created at every instance). On the other hand, reversing a StringBuilder is O(N) operation (reversing takes place within the same StringBuilder). In fact, reversing a String is not even possible in Java as for reversing a String, we need to change the characters of the already existing String and to change a character at a particular index of a String is not possible in Java (as there is no functionality to set a character at an index in a String in Java).
So, when we use StringBuilder, we will simply append the characters of the word in reverse order so that a reversed word is formed. This can be seen in the code given below.
#include<bits/stdc++.h>
using namespace std;
int main() {
string s = "Welcome to PrepBytes";
vector<string> v;
string temp = "";
for(int i=0;i<s.length();++i){
if(s[i]==' '){
v.push_back(temp);
temp = "";
}
else{
temp.push_back(s[i]);
}
}
v.push_back(temp);
string res = "";
for(int i=0;i<v.size();i++) {
string curr = v[i];
//reverse the current string
int lo = 0;
int hi = curr.length()-1;
while(lo < hi) {
char temp = curr[lo];
curr[lo] = curr[hi];
curr[hi] = temp;
lo++;
hi--;
}
res += curr;
if(i != v.size() -1) res += " ";
}
cout << res;
}
import java.util.*;
public class Main {
public static String reverseWords(String str) {
List<String> list = new ArrayList<>();
int idx = 0;
StringBuilder temp = new StringBuilder("");
while(idx < str.length()) {
char ch = str.charAt(idx);
if(ch == ' ') {
list.add(temp.toString());
temp = new StringBuilder("");
} else {
temp.append(ch);
}
idx++;
}
list.add(temp.toString());
StringBuilder res = new StringBuilder("");
for(int i=0;i<list.size();i++) {
String rev = reverse(list.get(i));
res.append(rev);
if(i != list.size() -1) res.append(" ");
}
return res.toString();
}
public static String reverse(String str) {
StringBuilder sb = new StringBuilder("");
for(int i=str.length() -1;i>=0;i--) {
sb.append(str.charAt(i));
}
return sb.toString();
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
String str = scn.nextLine();
String res = reverseWords(str);
System.out.println(res);
}
}
Time Complexity
If there are N words with an average length of L, then the time complexity of this approach is O(N * L). This is because we are traversing every word in the string to reverse it.
Space Complexity
The space complexity is also O(N * L) as we are maintaining an array of N words to reverse the words.
We cannot improve the time complexity in this case because we will have to traverse all the words in order to reverse them. However, we can improve the space complexity. Let us discuss the approach.
Space Optimised Approach (Using Stack)
So, let us consider a stack of characters and a pointer on the first index of the input string as shown below.
So, we have to insert the characters in the Stack the pointer on the input string encounters a space.
Now that the pointer has encountered a space, we pop each character from the stack and insert it into the output string. This will insert the reversed word into the string.
Before moving to the next word, add a space to the output string as well. Repeat the procedure again for the next word.
Now, for the last word, when the pointer reaches the end of the input string, we have to pop each character from the Stack and add it to the output string.
So, now that we have understood the procedure, let us write the code for the same.
#include <bits/stdc++.h>
using namespace std;
string reverseWords(string str)
{
stack<char> stk;
string res = "";
for (int i = 0; i < str.length(); ++i) {
if (str[i] != ' ')
stk.push(str[i]);
else {
while (stk.empty() == false) {
res += stk.top();
stk.pop();
}
res += " ";
}
}
while (stk.empty() == false) {
res += stk.top();
stk.pop();
}
return res;
}
int main()
{
string str = "Welcome to PrepBytes";
cout << reverseWords(str);
return 0;
}
import java.io.*;
import java.util.*;
class Main {
static String reverseWords(String str)
{
Stack<Character> stk = new Stack<Character>();
StringBuilder res = new StringBuilder("");
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch != ' ')
stk.push(ch);
else {
while (stk.empty() == false) {
res.append(stk.pop());
}
res.append(" ");
}
}
while (stk.empty() == false) {
res.append(stk.pop());
}
return res.toString();
}
public static void main(String[] args)
{
String str = "Welcome to PrepBytes";
System.out.println(reverseWords(str));
}
}
Time Complexity
The time complexity will be the same i.e. O(N * L) as we are traversing all the words in order to reverse them.
Space Complexity
The space complexity of this approach is O(L). This is because only one word is inserted at a time in the Stack.
Follow up on this approach
Can you reverse all the words with the same time and space complexity without the use of Stack? Think about it !!
The answer is Yes. Instead of using a stack to insert a word in it, you can simply reverse the string as we did in the first approach by taking an auxiliary string (or what we called a temporary string in the previous approach). Since we take an auxiliary string, the space complexity will be O(L).
In the case of the Java Program, we will take an auxiliary StringBuilder in place of a string.
Constant Space Solution (Possible in C++) with same Time Complexity
First, let us discuss the solution with constant space, and then we will discuss the reason why this solution is not possible in Java. (It is possible but not in constant space.)
So, the solution is pretty simple. We have 2 pointers both kept at the index 0 of the input string, initially.
Now, we move the high pointer till it encounters a space as shown below.
So, now we can keep a pointer i at low and j at high – 1. Then, we can reverse the word by swapping the ith and jth characters till i is less than j.
So, now we will have low = high + 1 and high = high + 1.
Now, we will keep on repeating the same procedure till low and high are less than the length of the string.
So, in this approach, we are not using any auxiliary String or Stack. Hence, the auxiliary space is constant i.e. Space complexity is constant.
However, this approach will work for C++ but not in Java. Why? Let us discuss the same.
Why won’t the above approach work in Java?
We are given a String in the input. Since the Strings in Java are immutable, we cannot set or change any character of a String in Java. (It is not allowed and such functionality is not present in Java). So, if we have to reverse, we will have to take a StringBuilder and if we take a StringBuilder, then we have taken an auxiliary space of size O(L). Hence, it will be the previous approach and not the current one.
So, this solution is not possible in Java.
Now that we have understood the procedure, let us write the code for the same.
#include <bits/stdc++.h>
using namespace std;
string reverse_words(string str)
{
int start = 0;
for (int i = 0; i <= str.size(); i++) {
if (str[i] == ' ' || i == str.size()) {
int end = i - 1;
while (start < end) {
swap(str[start], str[end]);
start++;
end--;
}
start = i + 1;
}
}
return str;
}
int main()
{
string str = "Welcome to PrepBytes";
cout << reverse_words(str);
return 0;
}
Time Complexity
The time complexity is O(N * L) since we are traversing all the N words of average length L.
Space Complexity
The space complexity is constant i.e. O(1) as we have not used any extra space in this approach.
So, these were the 3 solutions for the given problem. These are the standard problem-solving-based approaches for this question. However, there can be other ways also to solve this problem like Java 8 Streams can be used to solve this problem. Similarly, other libraries or STL in C++ can be used to solve this question.
However, solving the problem using some predefined methods is not allowed as per the constraints of the question. Hence, these 3 approaches are sufficient.
This article tried to discuss How to Reverse Individual Words. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.