今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
编辑:如果你发现了，公认的答案显然比这个更优雅、更有效。我把这个答案留给了我所做的，如果我没有想到将原始字符串加倍的话。
我就用蛮力。首先检查长度，然后尝试每一个可能的旋转偏移。如果没有，则返回false;如果有，则立即返回true。
没有特别的连接需要——只需使用指针(C)或索引(Java)，并在每个字符串中使用一个指针——从一个字符串的开头开始，在第二个字符串中使用当前的候选旋转偏移量，并在必要的地方进行换行。检查字符串中每个点的字符是否相等。如果你到达了第一个字符串的末尾，你就完成了。
它可能同样容易连接-尽管效率可能较低，至少在Java中是这样。
其他回答
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算法)
为什么不是这样的呢?
//is q a rotation of p?
bool isRotation(string p, string q) {
string table = q + q;
return table.IndexOf(p) != -1;
}
当然，你也可以编写自己的IndexOf()函数;我不确定。net使用的是一种简单的方式还是一种更快的方式。
天真:
int IndexOf(string s) {
for (int i = 0; i < this.Length - s.Length; i++)
if (this.Substring(i, s.Length) == s) return i;
return -1;
}
速度:
int IndexOf(string s) {
int count = 0;
for (int i = 0; i < this.Length; i++) {
if (this[i] == s[count])
count++;
else
count = 0;
if (count == s.Length)
return i - s.Length;
}
return -1;
}
编辑:我可能会有一些差一的问题;我不想检查。；）
反转其中一个字符串。取两者的FFT(将它们视为简单的整数序列)。将结果逐点相乘。使用反FFT转换回来。如果弦是彼此旋转的，那么结果将只有一个峰值——峰值的位置将由它们相对于彼此旋转的多少来指示。
纯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;
}
首先确保s1和s2的长度相同。然后检查s2是否是s1与s1连接的子字符串:
algorithm checkRotation(string s1, string s2)
if( len(s1) != len(s2))
return false
if( substring(s2,concat(s1,s1))
return true
return false
end
在Java中:
boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}
