Another question I cover in a presentationI’m preparingfor“Open University meets Open Source” meetups.

Thequestion

You have two strings, str1 and str2 and you need to return Trueif 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 defis_rotation(str1, str2): return(len(str1) == len(str2) and str1in str2*2)

I like thissolution 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 defis_rotation(str1, str2): if len(str1) != len(str2): return False for indexin 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

1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责；
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。