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?

  • 1
    Interesting concept of the classic reversal problem! Good question and welcome to Code Review :) – Alex L Jun 5 '15 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 Jun 5 '15 at 23:49
  • @Snowhawk04 The problem specifically says words. So, I dont think it applies to substrings as well. – Sarthak Singhal Jun 6 '15 at 13:44
up vote 4 down vote accepted

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";

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.