Reverse individual words

Problem Statement

The problem “Reverse individual words” states that you are given a string s. Now, print the reverse of all the individual words in the string.

Reverse individual words

Example

s = "TutorialCup - changing the way of learning"

puClairotuT - gnignahc eht yaw fo gninrael

 s = "Reverse individual words"

esreveR laudividni sdrow

Using Stack

Algorithm

Initialize a string of length n.
Create a stack data structure. Traverse through the string and check if the current character in the string is not white space. Then push the current character in the stack.
Else while the size of the stack is not 0, print the element at the top of the stack and then pop/remove it from the stack.
Now, after reaching the end of the string. Keep on printing the top of the stack and removing it while the stack is not empty.

Code

C++ Program to Reverse individual words

#include <bits/stdc++.h> 
using namespace std; 
  
void revWords(string str){ 
    stack<char> st; 
  
    for(int i = 0; i < str.length(); ++i){ 
        if(str[i] != ' '){ 
            st.push(str[i]);
        }
  
        else{ 
            while(st.empty() == false){ 
                cout << st.top(); 
                st.pop(); 
            } 
            cout << " "; 
        } 
    } 
  
    while(st.empty() == false){ 
        cout << st.top(); 
        st.pop(); 
    } 
} 
  
int main(){ 
    string s = "TutorialCup - changing the way of learning"; 
    
    revWords(s); 
    
    return 0; 
}

puClairotuT - gnignahc eht yaw fo gninrael

Java Program to Reverse individual words

import java.io.*; 
import java.util.*; 
  
class reverseWords{ 
  
    static void revWords(String str){
        
        Stack<Character> st=new Stack<Character>(); 
       
        for(int i = 0; i < str.length(); ++i){ 
            if(str.charAt(i) != ' '){ 
                st.push(str.charAt(i));
            }
       
            else{ 
                while (st.empty() == false){ 
                    System.out.print(st.pop()); 
                } 
                System.out.print(" "); 
            } 
        } 
       
        while(st.empty() == false){ 
            System.out.print(st.pop()); 
        } 
    } 
      
    public static void main(String[] args){ 
       String s = "TutorialCup - changing the way of learning"; 
        revWords(s); 
    } 
}

puClairotuT - gnignahc eht yaw fo gninrael

Complexity Analysis

Time Complexity

O(n) where n is the size of the string. We have simply traversed over all the characters from the string. Thus the time complexity is linear.

Space Complexity

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

Without Using Stack

Algorithm

Initialize a string of length n.
Create another string to reverse the original string. Traverse through the original string and check if the current character in the original string is not a white space. Then update the new string as concatenation of the current character and the new string.
Else print the new string and update the new string as blank.
Print the new string.

Code

C++ Program to Reverse individual words

#include <bits/stdc++.h> 
using namespace std; 
  
void revWords(string str){ 
    string s;
    
    for(int i = 0; i < str.length(); ++i){ 
        if(str[i] != ' '){ 
            s = str[i]+s;
        }
  
        else{ 
            cout << s <<" "; 
            s = "";
        } 
    } 
  
    cout << s;
} 
  
int main(){ 
    string s = "TutorialCup - changing the way of learning"; 
    
    revWords(s); 
    
    return 0; 
}

puClairotuT - gnignahc eht yaw fo gninrael

Java Program to Reverse individual words

import java.io.*; 
import java.util.*; 
  
class reverseWords{ 
  
    static void revWords(String str){
        
        String s = "";
        for(int i = 0; i < str.length(); ++i){ 
            if(str.charAt(i) != ' '){ 
                s = str.charAt(i)+s;
            }
       
            else{ 
                System.out.print(s+" ");
                s = "";
            } 
        } 
       
        System.out.print(s); 
    } 
      
    public static void main(String[] args){ 
       String s = "TutorialCup - changing the way of learning";
        revWords(s); 
    } 
}

puClairotuT - gnignahc eht yaw fo gninrael

Complexity Analysis

O(n^2) where n is the size of the string. We have traversed over the characters in the string. But the concatenation operation of a single character with the new string and storing it again into same string variable takes O(n) every time.

Space Complexity

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

Using C++ stringstream

Algorithm

Initialize a string of length n.
Create another string to reverse the original string. Create a stringstream object and pass the original string in it.
After that, traverse and read each word in the string and print it in reverse order.

Code

C++ Program to Reverse individual words

#include <bits/stdc++.h> 
using namespace std; 
  
void revWords(string str){ 
    
    string word; 
   
    stringstream s(str); 
   
    while(s >> word){ 
        reverse(word.begin(),word.end()); 
        cout<<word<<" "; 
    }
} 
  
int main(){ 
    string s = "TutorialCup - changing the way of learning"; 
    
    revWords(s); 
    
    return 0; 
}

puClairotuT - gnignahc eht yaw fo gninrael

Complexity Analysis

Time Complexity

O(n) where n is the size of the string. We have traversed over the characters in the string.

Space Complexity

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

Using Java 8 stream

Algorithm

Initialize a string of length n.
Create another string to reverse the original string. Reverse the words of original string using stream and join them together with which space using collector and store its result in the new string.
Print the new string.

Java Program to Reverse individual words

import java.io.*; 
import java.util.*;
import java.util.stream.Collectors; 
  
class reverseWords{ 
  
    static void revWords(String str){
        
        String result = Arrays.asList(str.split(" ")) 
                .stream() 
                .map(s -> new StringBuilder(s).reverse()) 
                .collect(Collectors.joining(" ")); 
  
        System.out.println(result);
    } 
      
    public static void main(String[] args){ 
        String s = "TutorialCup - changing the way of learning";
        revWords(s); 
    } 
}

puClairotuT - gnignahc eht yaw fo gninrael

Complexity Analysis

Time Complexity

O(n) where n is the size of the string. We have traversed over the characters in the string.

Space Complexity

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