Python: check if one string is a rotation of another string

Another question I cover in a presentation I’m preparing for “Open University meets Open Source” meetups.

The question

You have two strings, str1 and str2 and you need to return True if the first string is a rotation of the second string. Otherwise, return False.

Examples

“hello”,    “llohe” -> True. If we’ll rotate the second string twice, you’ll get ‘hello’.

“hello”,   “lloh”    -> False. ‘lloh” is not a rotation of the first string since it missing the character ‘e’. So same length is a basic requirement for the rotation check.

“hello”,  “ohlle”  -> False, no matter how many times you’ll rotate this string, you won’t get ‘hello’.

“hello”,   “ohell”  -> True. Rotate 4 times and you’ll get ‘hello”.

Short solution

def is_rotation(str1, str2):                                                                                                                          
    return(len(str1) == len(str2) and str1 in str2*2)

I like this solution since it’s quite clean and efficient. The first part is to make sure the strings have the same length. If the length is different, it means there is no rotation.

Next, we would check that str1 is a substring of twice str2. Let’s say we these two strings: (‘sye’, ‘yes’).  ‘sye’ is a substring of ‘yesyes’ and both ‘yes’ and ‘sye’ have the same length. It means there is a rotation 🙂

Slice solution

def is_rotation(str1, str2):                                                    
  if len(str1) != len(str2):                                                    
    return False                                                                
                                                                                
  for index in xrange(len(str1)):                                                                                           
    if str2.startswith(str1[index:]) and str2.endswith(str1[:index]):           
      return True                                                               
                                                                                
  return False

This solution is much longer as it doesn’t use ‘in’. Instead, we use slicing.

The beginning is similar, the first thing we check is that we have the same length for both strings.

Next we are looping through the length of the first string and each time we check if the second string matches the slicing of the first string at the beginning and the end of the second string, using  incremental variable. It’s much easier to illustrate what it does with small example:

Two strings: ‘yes’  and  ‘sye’.

First loop: ‘sye’ starts with ‘yes’ -> nope

Second loop: ‘sye’ starts with ‘ye’ -> nope

Third loop: ‘sye’ starts with ‘s’? yes. Also, ‘sye’ ends with ‘ye’? yes -> Bingo, we have a rotation 🙂

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s