第六版Cracking the Coding Interview题目1.9，题目如下：
String Rotation: Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (e.g., "waterbottle" is a rotation of "erbottlewat".
首先题目第一句假设了一种名为isSubstring的方法来检查一个字符串是不是包含在另一个字符串中。那么在Pyhton中主要有两种方法完成这个任务：
def isSubstring1(str1,str2):
return str1 in str2
def isSubstring2(str1,str2):
return str2.find(str1) > -1
上述isSubstring1和isSubstring2都可以检查str1是不是str2的子串，但是第一种写法更简洁明了一些，而且使用timeit测量运行时间发现第一种写法速度也稍快一些，所有推荐第一种写法。
接着具体分析问题，题中提到字符串rotation的概念，在rotation中，字符串被分为两部分并且调换顺序。比如在题目中提到的例子中：
s1 = xy = waterbottle
x = wat
y = erbottle
s2 = yx = erbottlewat
所以需要检查的是存不存在一个位置将s1分为x和y满足xy=s1和yx=s2。但是可以发现yx必然是xyxy的子串，也就是若rotation成立则s2肯定是s1s1的子串，反之若s2不为s1s1的子串则rotaion不成立。还需要注意的是判断s1和s2的长度，使用上面提到的in关键字判断isSubstring实现如下：
def stringRotation(str1, str2):
return (str2 in str1 + str1) if len(str1) == len(str2) else False
Comments