Return all words which have their reverse present in a string

Question

Problem Statement:

Given a string of words return all words which have their reverse present in the string as ( (word1 , reverseword1 ) , (word2 ,reverseword2) )

Example Case:

Input:

Sachin tendulkar is the best tseb eht nihcaS

Output:

{ ( best , tseb ) , ( the , eht) , (Sachin , nihcaS) }

My approach is to use a map and return the words if a match to the reverse of the current word is found in the map.

#include<iostream>
#include<unordered_map>
#include<string>

using namespace std;

int main()
{
unordered_map <string, int> binMap;
string test="Sachin tendulkar is the best tseb eht nihcaS si";
int i=0,j=0;
string temp,rev;
string::iterator it;
cout<<"{";

for(i = 0, it = test.begin() ; it <= test.end(); ++it)
    {   

        if(*it==' ' || it==test.end())
        {   
            temp=test.substr(j,i-j);
            rev=string(temp.rbegin(), temp.rend());
            if(binMap[rev]==1)
            cout<<"( "<<rev<<","<<temp<<" ), ";
            else
            binMap[temp]=1;
            j=i+1;
        }
        i++;
    }
cout<<"}";
return 0;
}

Is this the most optimal way to solve the problem or am I doing something wrong?

Interesting concept of the classic reversal problem! Good question and welcome to Code Review :) — Alex L
– Alex L, Commented Jun 5, 2015 at 14:40
Is this the actual problem statement? If so, I would expect to see substring matching. E.g. "This si" should produce {(si,is)} as "is" is present in the string "This si". — Snowhawk
– Snowhawk, Commented Jun 5, 2015 at 23:49
@Snowhawk04 The problem specifically says words. So, I dont think it applies to substrings as well. — Sarthak Singhal
– Sarthak Singhal, Commented Jun 6, 2015 at 13:44

Edward · Accepted Answer · 2015-06-06 13:53:08Z

I have observed a few things that may help you improve your code.

Use library functions

One of the things the code does is to separate words in the input. However, this could be done more easily by using a std::stringstream:

stringstream in(test);
string word;
while (in >> word) {
    // test each word
}

Use more whitespace to enhance readability of the code

Instead of crowding things together like this:

cout<<"( "<<rev<<","<<temp<<" ), ";

most people find it more easily readable if you use more space:

cout << "( " << rev << ", " << word << " ) ";

Only print words once

Right now, with this input string:

string test="Sachin tendulkar is si is the best tseb eht nihcaS si";

The word "is" gets reported twice.

{( is,si ), ( best,tseb ), ( the,eht ), ( Sachin,nihcaS ), ( is,si ), }

One way to handle that is to note when each word is actually reported and to only do it once. Here's one way to do that:

stringstream in(test);
enum state { DETECTED=1, REPORTED };
unordered_map <string, state> binMap;

string word;
cout << "{";
while (in >> word) {
    string rev{word.rbegin(), word.rend()};
    if (binMap[rev] == DETECTED && binMap[word] != REPORTED) {
        cout << "( " << rev << ", " << word << " ) ";
        binMap[word] = REPORTED;
    } else {
        binMap[word] = DETECTED;
    }
}
cout << "}\n";

janos · Accepted Answer · 2015-06-05 16:28:58Z

There are several choosing style issues that make this hard to read and understand:

The variables i and j would be so much better as wordEnd and wordStart
The indentation is lacking inside the innermost if statement, and inconsistent and weird throughout
Many of the variables should have been declared inside the for statement to minimize their scope
using namespace std is considered bad practice

This program would be a lot easier to play with and to test if it took the test string as a command line argument.

I suppose you called binMap that way because it will only contain 0 or 1 as values. In that case int is the wrong value type. Boolean wouldn't be the right type either, because a map with binary values could probably be a set. You could have used the int as a counter to avoid printing the same values twice. But even so, only a few int values would be used. So the best solution is what Edward proposed.

Stack Exchange Network

Return all words which have their reverse present in a string

2 Answers 2

Use library functions

Use more whitespace to enhance readability of the code

Only print words once

You must log in to answer this question.

Hot Network Questions

Return all words which have their reverse present in a string

2 Answers 2

Use library functions

Use more whitespace to enhance readability of the code

Only print words once

You must log in to answer this question.

Related

Hot Network Questions