今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
当然，更好的答案应该是，“嗯，我会问stackoverflow社区，可能会在5分钟内得到至少4个非常好的答案”。有头脑是很好的，但我更看重那些知道如何与他人合作找到解决方案的人。
其他回答
Opera的简单指针旋转技巧是有效的，但是在运行时最糟糕的情况下效率极低。简单地想象一个有许多长重复字符的字符串，例如:
S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2 S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1
从计算角度来看，“循环直到出现不匹配，然后再加1，再试一次”是一种可怕的方法。
为了证明你可以毫不费力地在C语言中使用串联方法，下面是我的解决方案:
int isRotation(const char* s1, const char* s2) {
assert(s1 && s2);
size_t s1Len = strlen(s1);
if (s1Len != strlen(s2)) return 0;
char s1SelfConcat[ 2 * s1Len + 1 ];
sprintf(s1SelfConcat, "%s%s", s1, s1);
return (strstr(s1SelfConcat, s2) ? 1 : 0);
}
这在运行时间上是线性的，以开销中O(n)内存使用为代价。
(请注意，strstr()的实现是特定于平台的，但如果特别脑死亡，总是可以用更快的替代方案替代，如Boyer-Moore算法)
下面是一个使用正则表达式的例子，只是为了好玩:
boolean isRotation(String s1, String s2) {
return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}
如果可以使用保证不在任何字符串中出现的特殊分隔符，可以使它更简单一些。
boolean isRotation(String s1, String s2) {
// neither string can contain "="
return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}
你也可以使用有限重复的回溯:
boolean isRotation(String s1, String s2) {
return (s1 + s2).matches(
String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
);
}
使用strlen和strpos函数在PHP中很容易编写:
function isRotation($string1, $string2) {
return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}
我不知道strpos内部使用什么，但如果它使用KMP，它将在时间上是线性的。
不确定这是否是最有效的方法，但它可能相对有趣:Burrows-Wheeler变换。根据WP文章，输入的所有旋转产生相同的输出。对于压缩等应用程序，这是不可取的，所以原始旋转被指示(例如通过索引;参见文章)。但对于简单的与旋转无关的比较，这听起来很理想。当然，这并不一定是理想的效率!
纯Java答案(无空检查)
private boolean isRotation(String s1,String s2){
if(s1.length() != s2.length()) return false;
for(int i=0; i < s1.length()-1; i++){
s1 = new StringBuilder(s1.substring(1)).append(s1.charAt(0)).toString();
//--or-- s1 = s1.substring(1) + s1.charAt(0)
if(s1.equals(s2)) return true;
}
return false;
}
