Reverse words in a string

Problem Statement

“Reverse words in a string” states that you are given a string s of size n. Print the string in reverse order such that the last word becomes the first, second last becomes the second, and so on. Hereby string we refer to a sentence containing words instead of a word consisting of characters.

Example

s = "TutorialCup makes learning easy"

easy learning makes TutorialCup

Explanation: TutorialCup is the first word thus on reversing it goes to the end. The last word “easy” goes to the front and other words are reversed in a similar fashion. More Formally,

Let the given string s = “TutorialCup makes learning easy” , res = ” ” , begin =0, end = n-1.

Start traversing the string through the end –

Step 1 – At index 26, s[i] = ‘ ‘, Therefore,

begin = 27, res = “easy ”

Step 2 – At index 17, s[i] = ‘ ‘, Therefore,

begin = 18, res = “easy learning ”

Step 3 – At index 11, s[i] = ‘ ‘, Therefore,

begin = 12, res = “easy learning makes ”

Step 4 – begin = 0

res = “easy learning makes TutorialCup”

s = "Contributed by Akshita Jain"

Jain Akshita by Contributed

Algorithm for reverse words in a string problem

1. Initialize a string s of size n.
2. Create a function to reverse the words of the given string which accepts a string variable as it's a parameter.
3. After that, create two variables of integer type begin and end. Initialize the variable end as the size of the string.
4. Create an empty string variable to store the result.
5. Traverse through the string from the last character to first and check if the character at current index in the given string is a white space, update the variable begin as current index + 1 and while variable begin is not equal to the variable end, add the character at index begin + 1 of the given string in the result string variable.
6. Add a white space in the result string variable and update the variable end as the current index.
7. Update variable begin as 0.
8. Traverse again, while variable begin is not equal to variable end, add the character at index begin + 1 of the given string in the result string variable.
9. Return the resulting string variable.

A string is simply a collection of characters. So by string, we may say that it is a word or it is a sentence. But when we say a string is a word. We mean that the string does not contain any space in between. But when refer a sentence using string, we also consider the case where there may be spaces in between the characters. So, one should knot get confused over word or sentence with respect to a string.

Code

C++ Program to reverse the words in a string

#include<bits/stdc++.h> 
using namespace std; 
  
string reverseStringWords(string s){ 
    int i = s.length() - 1, begin, end = i + 1; 
    string res = ""; 
      
    while(i >= 0){ 
        if(s[i] == ' '){ 
            begin = i + 1; 
            while(begin != end) 
                res += s[begin++]; 
              
            res += ' '; 
            end = i; 
        } 
        
        i--; 
    } 
    begin = 0; 
    while(begin != end) 
        res += s[begin++]; 
      
    return res; 
} 
  
int main(){ 
    string s = "TutorialCup makes learning easy"; 
    cout << reverseStringWords(s); 
      
    return 0; 
} 

easy learning makes TutorialCup

Java Program to reverse the words in a string

import java.io.*; 
import java.util.*; 
import java.lang.*; 
  
class reverse{ 
    static String reverseStringWords(String s){ 
        int i = s.length() - 1; 
        int begin, end = i + 1; 
        String res = ""; 
          
        while(i >= 0){ 
            if(s.charAt(i) == ' '){ 
                begin = i + 1; 
                while(begin != end) 
                    res += s.charAt(begin++); 
                  
                res += ' '; 
                  
                end = i; 
            } 
            i--; 
        } 
          
        begin = 0; 
        while(begin != end) 
            res += s.charAt(begin++); 
          
        return res; 
    } 
      
    public static void main(String[] args){ 
        String s = "TutorialCup makes learning easy"; 
          
        System.out.print(reverseStringWords(s)); 
    } 
} 

easy learning makes TutorialCup

Complexity Analysis

Time Complexity

O(n) where n is the total number of characters in the given string.

Space Complexity

O(n) because we used space to store n elements.