今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
我在Perl中这样做:
sub isRotation {
return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1;
}
其他回答
int rotation(char *s1,char *s2)
{
int i,j,k,p=0,n;
n=strlen(s1);
k=strlen(s2);
if (n!=k)
return 0;
for (i=0;i<n;i++)
{
if (s1[0]==s2[i])
{
for (j=i,k=0;k<n;k++,j++)
{
if (s1[k]==s2[j])
p++;
if (j==n-1)
j=0;
}
}
}
if (n==p+1)
return 1;
else
return 0;
}
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算法)
目前还没有人提供模数方法，所以这里有一个:
static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "tackoverflwos"));
Console.ReadLine();
}
public static bool IsRotation(string a, string b)
{
Console.WriteLine("\nA: {0} B: {1}", a, b);
if (b.Length != a.Length)
return false;
int ndx = a.IndexOf(b[0]);
bool isRotation = true;
Console.WriteLine("Ndx: {0}", ndx);
if (ndx == -1) return false;
for (int i = 0; i < b.Length; ++i)
{
int rotatedNdx = (i + ndx) % b.Length;
char rotatedA = a[rotatedNdx];
Console.WriteLine( "B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA );
if (b[i] != rotatedA)
{
isRotation = false;
// break; uncomment this when you remove the Console.WriteLine
}
}
return isRotation;
}
输出:
A: stackoverflow B: ztackoverflow
Ndx: -1
Rotation : False
A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True
A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True
A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
Rotation : False
A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
B: s A[0]: s
Rotation : False
(编辑:2010-04-12)
Piotr注意到了我上面代码中的缺陷。当字符串中的第一个字符出现两次或两次以上时，将出错。例如，针对owstackoverflow测试的stackoverflow结果为false，而实际上应该为true。
感谢piotr发现了这个错误。
现在，这是修正后的代码:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace TestRotate
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "tackoverflwos"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "owstackoverfl"));
Console.ReadLine();
}
public static bool IsRotation(string a, string b)
{
Console.WriteLine("\nA: {0} B: {1}", a, b);
if (b.Length != a.Length)
return false;
if (a.IndexOf(b[0]) == -1 )
return false;
foreach (int ndx in IndexList(a, b[0]))
{
bool isRotation = true;
Console.WriteLine("Ndx: {0}", ndx);
for (int i = 0; i < b.Length; ++i)
{
int rotatedNdx = (i + ndx) % b.Length;
char rotatedA = a[rotatedNdx];
Console.WriteLine("B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA);
if (b[i] != rotatedA)
{
isRotation = false;
break;
}
}
if (isRotation)
return true;
}
return false;
}
public static IEnumerable<int> IndexList(string src, char c)
{
for (int i = 0; i < src.Length; ++i)
if (src[i] == c)
yield return i;
}
}//class Program
}//namespace TestRotate
输出如下:
A: stackoverflow B: ztackoverflow
Rotation : False
A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True
A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True
A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False
A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False
A: stackoverflow B: owstackoverfl
Ndx: 5
B: o A[5]: o
B: w A[6]: v
Ndx: 11
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
Rotation : True
这是lambda方法:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace IsRotation
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "owstackoverfl"));
string strToTestFrom = "stackoverflow";
foreach(string s in StringRotations(strToTestFrom))
{
Console.WriteLine("is {0} rotation of {1} ? {2}",
s, strToTestFrom,
IsRotation(strToTestFrom, s) );
}
Console.ReadLine();
}
public static IEnumerable<string> StringRotations(string src)
{
for (int i = 0; i < src.Length; ++i)
{
var sb = new StringBuilder();
for (int x = 0; x < src.Length; ++x)
sb.Append(src[(i + x) % src.Length]);
yield return sb.ToString();
}
}
public static bool IsRotation(string a, string b)
{
if (b.Length != a.Length || a.IndexOf(b[0]) < 0 ) return false;
foreach(int ndx in IndexList(a, b[0]))
{
int i = ndx;
if (b.ToCharArray().All(x => x == a[i++ % a.Length]))
return true;
}
return false;
}
public static IEnumerable<int> IndexList(string src, char c)
{
for (int i = 0; i < src.Length; ++i)
if (src[i] == c)
yield return i;
}
}//class Program
}//namespace IsRotation
下面是lambda方法的输出:
Rotation : False
Rotation : True
Rotation : True
Rotation : False
Rotation : True
is stackoverflow rotation of stackoverflow ? True
is tackoverflows rotation of stackoverflow ? True
is ackoverflowst rotation of stackoverflow ? True
is ckoverflowsta rotation of stackoverflow ? True
is koverflowstac rotation of stackoverflow ? True
is overflowstack rotation of stackoverflow ? True
is verflowstacko rotation of stackoverflow ? True
is erflowstackov rotation of stackoverflow ? True
is rflowstackove rotation of stackoverflow ? True
is flowstackover rotation of stackoverflow ? True
is lowstackoverf rotation of stackoverflow ? True
is owstackoverfl rotation of stackoverflow ? True
is wstackoverflo rotation of stackoverflow ? True
使用strlen和strpos函数在PHP中很容易编写:
function isRotation($string1, $string2) {
return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}
我不知道strpos内部使用什么，但如果它使用KMP，它将在时间上是线性的。
当然，更好的答案应该是，“嗯，我会问stackoverflow社区，可能会在5分钟内得到至少4个非常好的答案”。有头脑是很好的，但我更看重那些知道如何与他人合作找到解决方案的人。
