Modify a sentence by reversing order of occurrences of all Palindrome Words

0 0 6 minutes read

Given a string S representing a sentence, the task is to reverse the order of all palindromic words present in the sentence.

Examples:

Input: S = “mom and dad went to eye hospital”
Output: eye and dad went to mom hospital
Explanation: All palindromic words present in the string are “mom”, “dad” and “eye“, in the order of their occurrence. Reversing the order of their occurrence generates the sequence {“eye”, “dad”, “mom”}. Therefore, the modified string is “eye and dad went to mom hospital”.

Input : S = “wow it is next level”
Output: level it is next wow.

Approach: Follow the steps below to solve the problem:

Iterate over the characters of the string S and split the space-separated words from the sentence using split() and store them in a list, say lis.
Append all the palindromic words to a new list, say newlist, using append() function.
Reverse this new list using reverse() function.
Traverse the list lis and keep replacing the palindromic words with the newlist[i] ( initially, i=0 ) and increment i by 1.
Print the modified sentence

Below is the implementation of the above approach:

Java

// Java implementation of
// the above approach
import java.util.*;
 
class GFG{
     
// Function to check if a
// string S is a palindrome
static boolean palindrome(String str)
{
    int st = 0;
    int ed = str.length() - 1;
 
    while (st < ed)
    {
        if (str.charAt(st) == str.charAt(ed)) 
        {
            st++;
            ed--;
        }
        else
            return false;
    }
    return true;
}
 
// Function to print the modified string
// after reversing the order of occurrences
// of all palindromic words in the sentence
static void printReverse(String sentence)
{
     
    // Stores the palindromic words
    ArrayList<String> newlist = new ArrayList<String>();
    ArrayList<String> lis = new ArrayList<String>();
 
    // Stores the words in the list
    String temp = "";
 
    for(char x: sentence.toCharArray())
    {
        if (x == ' ') 
        {
            lis.add(temp);
            temp = "";
        }
        else
            temp += x;
    }
    lis.add(temp);
 
    // Traversing the list
    for(String x:  lis)
    {
 
        // If current word is a palindrome
        if (palindrome(x))
 
            // Update newlist
            newlist.add(x);
    }
 
    // Reverse the newlist
    Collections.reverse(newlist);
 
    int j = 0;
 
    // Traverse the list
    for(int i = 0; i < lis.size(); i++) 
    {
         
        // If current word is a palindrome
        if (palindrome(lis.get(i))) 
        {
             
            // Update lis[i]
            lis.set(i,newlist.get(j));
 
            // Increment j
            j = j + 1;
        }
    }
 
    // Print the updated sentence
    for(String x : lis) 
        System.out.print(x + " ");
}
 
// Driver code
public static void main(String[] args)
{
    String sentence = "mom and dad went to eye hospital";
    printReverse(sentence);
}
}
 
// This code is contributed by offbeat

Python3

# Python implementation of
# the above approach
 
# Function to check if a 
# string S is a palindrome
def palindrome(string):
   
    if(string == string[::-1]):
        return True
    else:
        return False
 
# Function to print the modified string
# after reversing the order of occurrences
# of all palindromic words in the sentence
def printReverse(sentence):
   
    # Stores the palindromic words
    newlist = []
     
    # Stores the words in the list
    lis = list(sentence.split())
     
    # Traversing the list
    for i in lis:
       
        # If current word is a palindrome
        if(palindrome(i)):
           
              # Update newlist
            newlist.append(i)
 
    # Reverse the newlist
    newlist.reverse()
     
    j = 0
     
    # Traverse the list
    for i in range(len(lis)):
       
        # If current word is a palindrome
        if(palindrome(lis[i])):
           
            # Update lis[i]
            lis[i] = newlist[j]
             
            # Increment j
            j = j + 1
 
    # Print the updated sentence
    for i in lis:
        print(i, end =" ")
 
 
# Driver Code
 
sentence = "mom and dad went to eye hospital"
printReverse(sentence)

C#

// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to check if a
// string S is a palindrome
static bool palindrome(string str)
{
    int st = 0;
    int ed = str.Length - 1;
 
    while (st < ed)
    {
        if (str[st] == str[ed]) 
        {
            st++;
            ed--;
        }
        else
            return false;
    }
    return true;
}
 
// Function to print the modified string
// after reversing the order of occurrences
// of all palindromic words in the sentence
static void printReverse(string sentence)
{
     
    // Stores the palindromic words
    List<string> newlist = new List<string>();
    List<string> lis = new List<string>();
 
    // Stores the words in the list
    string temp = "";
 
    foreach(char x in sentence)
    {
        if (x == ' ') 
        {
            lis.Add(temp);
            temp = "";
        }
        else
            temp += x;
    }
    lis.Add(temp);
 
    // Traversing the list
    foreach(string x in lis)
    {
 
        // If current word is a palindrome
        if (palindrome(x))
 
            // Update newlist
            newlist.Add(x);
    }
 
    // Reverse the newlist
    newlist.Reverse();
 
    int j = 0;
 
    // Traverse the list
    for(int i = 0; i < lis.Count; i++) 
    {
         
        // If current word is a palindrome
        if (palindrome(lis[i])) 
        {
             
            // Update lis[i]
            lis[i] = newlist[j];
 
            // Increment j
            j = j + 1;
        }
    }
 
    // Print the updated sentence
    foreach(string x in lis) 
        Console.Write(x + " ");
}
 
// Driver Code
public static void Main()
{
    string sentence = "mom and dad went to eye hospital";
    printReverse(sentence);
}
}
 
// This code is contributed by ukasp

Javascript

<script>
// Javascript implementation of
// the above approach
 
// Function to check if a 
// string S is a palindrome
function palindrome(str)
{
    var st = 0;
    var ed = str.length - 1;
     
    while (st < ed)
    {
        if (str[st] == str[ed])
        {
            st++;
            ed--;
        }
        else
          return false;
    }
    return true;
}
 
// Function to print the modified string
// after reversing the order of occurrences
// of all palindromic words in the sentence
function printReverse(sentence)
{
     
    // Stores the palindromic words
    var newlist = [];
    var lis = [];
     
    // Stores the words in the list
    var temp = "";
     
    for(var i =0; i<sentence.length;i++)
    {
        if (sentence[i] == ' ')
        {
            lis.push(temp);
            temp = "";
        }
        else
            temp += sentence[i];
    }
    lis.push(temp);
     
    // Traversing the list
    for(var i =0; i<lis.length;i++)
    {
         
        // If current word is a palindrome
        if (palindrome(lis[i]))
         
            // Update newlist
            newlist.push(lis[i]);
    }
 
    // Reverse the newlist
    newlist.reverse();
     
    var j = 0;
     
    // Traverse the list
    for(var i = 0; i < lis.length; i++)
    {
         
        // If current word is a palindrome
        if (palindrome(lis[i]))
        {
             
            // Update lis[i]
            lis[i] = newlist[j];
             
            // Increment j
            j = j + 1;
        }
    }
 
    // Print the updated sentence
    for(var i = 0; i < lis.length; i++)
    {
       document.write( lis[i] + " ");
    }
}
 
// Driver Code
var sentence = "mom and dad went to eye hospital";
printReverse(sentence);
 
</script>

C++

// C++ implementation of the above approach
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
// Function to check if a
// string S is a palindrome
bool palindrome(string str)
{
    int st = 0;
    int ed = str.length() - 1;
 
    while (st < ed)
    {
        if (str[st] == str[ed]) 
        {
            st++;
            ed--;
        }
        else
            return false;
    }
    return true;
}
 
// Function to print the modified string
// after reversing the order of occurrences
// of all palindromic words in the sentence
void printReverse(string sentence)
{
     
    // Stores the palindromic words
    vector<string> newlist;
    vector<string> lis;
 
    // Stores the words in the list
    string temp = "";
 
    for(char x: sentence)
    {
        if (x == ' ') 
        {
            lis.push_back(temp);
            temp = "";
        }
        else
            temp += x;
    }
    lis.push_back(temp);
 
    // Traversing the list
    for(string x:  lis)
    {
 
        // If current word is a palindrome
        if (palindrome(x))
 
            // Update newlist
            newlist.push_back(x);
    }
 
    // Reverse the newlist
    reverse(newlist.begin(), newlist.end());
 
    int j = 0;
 
    // Traverse the list
    for(int i = 0; i < lis.size(); i++) 
    {
         
        // If current word is a palindrome
        if (palindrome(lis[i])) 
        {
             
            // Update lis[i]
            lis[i] = newlist[j];
 
            // Increment j
            j = j + 1;
        }
    }
 
    // Print the updated sentence
    for(string x : lis) 
        cout << x << " ";
}
 
// Driver code
int main()
{
    string sentence = "mom and dad went to eye hospital";
    printReverse(sentence);
    return 0;
}
 
// Contributed by adityashae15

Output:

eye and dad went to mom hospital

Time Complexity: O(N)
Auxiliary Space: O(N) because it is using extra space for list newlist and lis

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!