Is a String rotated or not?

“A Simple word within a word. But little bit tricky if you did not think in normal way.”

Introduction

    A very simple interview question,

You have a string like “simple”

You are given a string “esimpl”. You need to verify whether the given string is just a rotation of the original string.

How will you detect rotations in general terms? We go thru the elements and find the place where the shift happened. From there we start comparing. But that will complicate things for the given problem.

Concept

   The simple way is to just concat the replica of the rotated string:

“esimplesimpl”

When you do concat, you see that, simple is again getting recreated in the buffer. Then to check whether its really a rotation, it becomes so simple, just search for base string “simple” within the concat string.

There is one more condition which reduces the time taken to search inside string, The string Length.

Code

/*

Whether the string is rotated or not?

simple

plesim

*/

bool isRotated(char* input, char* rotated)

{

    if(strlen(input) != strlen(rotated))

        return false;

    char* buff = (char*) malloc(strlen(rotated)*2);

    strcat(buff, rotated);

    strcat(buff, rotated);

    char* pos = strstr(buff, input);

    if(pos != NULL)

        return true;

    else

        return false;

}

void main()

{

    bool test = isRotated("simple", "esimpl");

}

Important points:

• This is the simplest code and it is self understandable
• The only place where this is useful is in a spell checker application :)
• Just try “esimple” in a winword document, spell checker will detect that as an error and gives you a matching suggestion from the dictionary. :)