Kotlin程序员：判断字符串旋转的方法

【出自WR面试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

给定一个能判断一个单词是否为另一个单词的子字符串的方法，记为isSubstring。如何判断s2是否能通过旋转s1得到（只能使用一次isSubstring方法）。例如：“waterbottle”可以通过字符串“erbottlewat”旋转得到。

分析与解答：

如果题目没有对isString使用的限制，可以通过求出s2进行旋转的所有组合，然后与s1进行比较。但是这种方法的时间复杂度比较高。通过对字符串旋转进行仔细分析，发现对字符串s1进行旋转得到的字符串一定是s1s1的子串。因此可以通过判断s2是否是s1s1的子串来判断s2能够通过旋转s1得到。例如：s1=“waterbottle”，那么s1s1=“waterbottlewaterbottle”，显然s2是s1s1的子串，因此s2能通过旋转s1得到。实现代码如下：(www.xing528.com)

程序的运行结果如下：

erbottlewat可以通过旋转waterbottle得到

为了简单起见，这种方法中isSubstring通过调用库函数的方式进行了实现，当然在采用KMP算法实现的isSubstring的效率最高。

算法性能分析：

这种方法首先对字符串str1进行了一次遍历，时间复杂度为O（N）（其中，N为字符串的长度），接着调用了isSubstring函数（假设采用了KMP算法），这种方法的时间复杂度为O（2N+N）=O（3N），因此，整个算法的时间复杂度为O（N）。此外这种方法申请了2N+1个存储空间，因此，算法的空间复杂度也为O（N）。