Home > Applied Algorithms, String > Rotated String conundrum

Rotated String conundrum

Problem Statement: You have an original string and its rotated version as input. (Eg. Original string = hello, Rotated string = llohe) You need to tell how many places the original string needs to be rotated by to get the rotated string.

You can come up with multiple approaches here, all of which are bullshit and not efficient. I have only been able to find a single method which gives me acceptable efficiency.

Solution: You should append the rotated string at the end of another instance of the rotated string and then find the original string in it. And your answer will be length of string minus the starting position of the found substring (original string)

Eg. llohellohe (appended llohe after llohe πŸ˜‰ )

So I search fot he original string β€˜hello’. This gives me the starting position 3 (index from 0). So rotation = (5-3) = 2

EDIT:Β You can implement this in a better way by indexing the original string as i%string.length where i will range from 0 to twice the string length. You are effectively going twice through the rotated string while searching for the substring. – Contributed by Sanjoy (due credits πŸ˜‰ )

Pretty easy, eh? πŸ™‚

Advertisements
  1. sanjoydas
    April 7, 2012 at 8:41 pm

    Why do you need to append anything? Just search (using KMP or whatever) in the original string, and index this way:

    char idx(string str, int idx) { return str[idx % str.length()]; }

  2. April 7, 2012 at 8:48 pm

    Eh? Sorry dude didn’t get it. πŸ™‚ Can you give an example?

    • sanjoydas
      April 7, 2012 at 8:55 pm

      Assuming m is the morphed word and str is the unmorphed word, instead of getting the ith character from m as m[i], pretend the ith character is m[i % m.length()]. In this scheme, the 5th character in llohe is l, the 6th char is l and so on …

      This is effectively the same as your approach, except that you can do it in constant memory.

      • April 7, 2012 at 8:57 pm

        Haha! Nice! Didn’t think about that. Let me edit the post. πŸ™‚ Thanks!

  3. Prateek
    November 16, 2012 at 6:31 pm

    Can it be something like this :
    while (orgstr!=rotstr) {
    for(i=0;i<len;i++)
    str[((i+1)%len)] = str[i];
    rot++;
    }

    In this after completion of inner for loop, my str is rotated by 1 char to right. After each rotation i check if it is equal to rotatedstring given in the question.

    Problem is i dont understand how to compare two algorithms for efficiency. like which one is better. Can you please tell the efficiency of your algorithm and mine as well. So i can understand how to identify a better algorithm.

    Thank you.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: