面试问题:检查一个字符串是否是另一个字符串的旋转

今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:

给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?

例子:

如果s1 = "stackoverflow"，则以下是它的一些旋转版本:

"tackoverflows"
"ackoverflowst"
"overflowstack"

其中“stackoverflwo”不是一个旋转的版本。

他给出的答案是:

取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1

对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?

提前谢谢你。

当前回答

我想最好在Java中这样做:

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}

在Perl中我会这样做:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}

或者更好的使用index函数而不是regex:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}

其他回答

我在Perl中这样做:

sub isRotation { 
     return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1; 
}

编辑:如果你发现了，公认的答案显然比这个更优雅、更有效。我把这个答案留给了我所做的，如果我没有想到将原始字符串加倍的话。

我就用蛮力。首先检查长度，然后尝试每一个可能的旋转偏移。如果没有，则返回false;如果有，则立即返回true。

没有特别的连接需要——只需使用指针(C)或索引(Java)，并在每个字符串中使用一个指针——从一个字符串的开头开始，在第二个字符串中使用当前的候选旋转偏移量，并在必要的地方进行换行。检查字符串中每个点的字符是否相等。如果你到达了第一个字符串的末尾，你就完成了。

它可能同样容易连接-尽管效率可能较低，至少在Java中是这样。

连接string1和string2，使用KMP算法检查string2是否出现在新形成的字符串中。因为KMP的时间复杂度小于substr。

使用strlen和strpos函数在PHP中很容易编写:

function isRotation($string1, $string2) {
    return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}

我不知道strpos内部使用什么，但如果它使用KMP，它将在时间上是线性的。

另一个python示例(基于答案):

def isrotation(s1,s2):
     return len(s1)==len(s2) and s1 in 2*s2

推荐文章