今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
为什么不是这样的呢?
//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;
}
编辑:我可能会有一些差一的问题;我不想检查。；）
其他回答
为什么不是这样的呢?
//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;
}
编辑:我可能会有一些差一的问题;我不想检查。；）
首先，确保两根弦的长度相同。然后在C中，你可以用一个简单的指针迭代来实现。
int is_rotation(char* s1, char* s2)
{
char *tmp1;
char *tmp2;
char *ref2;
assert(s1 && s2);
if ((s1 == s2) || (strcmp(s1, s2) == 0))
return (1);
if (strlen(s1) != strlen(s2))
return (0);
while (*s2)
{
tmp1 = s1;
if ((ref2 = strchr(s2, *s1)) == NULL)
return (0);
tmp2 = ref2;
while (*tmp1 && (*tmp1 == *tmp2))
{
++tmp1;
++tmp2;
if (*tmp2 == '\0')
tmp2 = s2;
}
if (*tmp1 == '\0')
return (1);
else
++s2;
}
return (0);
}
另一个python示例(基于答案):
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
将每个字符作为振幅，并对其进行离散傅里叶变换。如果它们仅因旋转而不同，则频谱将在舍入误差范围内相同。当然，这是低效的，除非长度是2的幂，所以你可以做FFT:-)
另一个基于答案的Ruby解决方案:
def rotation?(a, b); a.size == b.size and (b*2)[a]; end
