今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
首先确保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);
}
编辑:如果你发现了，公认的答案显然比这个更优雅、更有效。我把这个答案留给了我所做的，如果我没有想到将原始字符串加倍的话。
我就用蛮力。首先检查长度，然后尝试每一个可能的旋转偏移。如果没有，则返回false;如果有，则立即返回true。
没有特别的连接需要——只需使用指针(C)或索引(Java)，并在每个字符串中使用一个指针——从一个字符串的开头开始，在第二个字符串中使用当前的候选旋转偏移量，并在必要的地方进行换行。检查字符串中每个点的字符是否相等。如果你到达了第一个字符串的末尾，你就完成了。
它可能同样容易连接-尽管效率可能较低，至少在Java中是这样。
另一个python示例(基于答案):
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
首先，确保两根弦的长度相同。然后在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);
}
下面是一个使用正则表达式的例子，只是为了好玩:
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())
);
}
由于其他人已经提交了二次最坏情况时间复杂度解决方案，我将添加一个线性解决方案(基于KMP算法):
bool is_rotation(const string& str1, const string& str2)
{
if(str1.size()!=str2.size())
return false;
vector<size_t> prefixes(str1.size(), 0);
for(size_t i=1, j=0; i<str1.size(); i++) {
while(j>0 && str1[i]!=str1[j])
j=prefixes[j-1];
if(str1[i]==str1[j]) j++;
prefixes[i]=j;
}
size_t i=0, j=0;
for(; i<str2.size(); i++) {
while(j>0 && str2[i]!=str1[j])
j=prefixes[j-1];
if(str2[i]==str1[j]) j++;
}
for(i=0; i<str2.size(); i++) {
if(j>=str1.size()) return true;
while(j>0 && str2[i]!=str1[j])
j=prefixes[j-1];
if(str2[i]==str1[j]) j++;
}
return false;
}
工作示例
当然，更好的答案应该是，“嗯，我会问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算法)
目前还没有人提供模数方法，所以这里有一个:
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
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;
}
我想最好在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;
}
不确定这是否是最有效的方法，但它可能相对有趣:Burrows-Wheeler变换。根据WP文章，输入的所有旋转产生相同的输出。对于压缩等应用程序，这是不可取的，所以原始旋转被指示(例如通过索引;参见文章)。但对于简单的与旋转无关的比较，这听起来很理想。当然，这并不一定是理想的效率!
C#:
s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)
哇,哇……为什么每个人都对O(n²)的答案如此兴奋?我相信我们可以做得更好。上面的答案包括O(n)循环中的O(n)操作(substring/indexOf调用)。即使有更高效的搜索算法;比如Boyer-Moore或KMP，最坏情况仍然是O(n^2)有重复。
O(n)随机化的答案很简单;取一个支持O(1)滑动窗口的哈希值(如Rabin指纹);哈希字符串1，然后哈希字符串2，然后继续围绕字符串移动哈希1的窗口，看看哈希函数是否冲突。
如果我们想象最坏的情况是“扫描两条DNA链”，那么碰撞的概率就会上升，这可能退化为O(n^(1+e))或其他(只是猜测)。
最后，有一个确定的O(nlogn)解，它有一个非常大的常数。基本上，就是对两个弦进行卷积。卷积的最大值将是旋转差(如果它们被旋转);O(n)检查确认。好处是如果有两个相等的最大值，那么它们也是有效解。你可以用两个FFT进行卷积一个点积，一个iFFT，所以nlogn + nlogn + n + nlogn + n = O(nlogn)
因为你不能用0填充，你不能保证字符串的长度是2^n, fft不会是最快的;它们会变慢，仍然是O(nlogn)，但比CT算法大得多。
说了这么多，我绝对，100%肯定这里有一个确定的O(n)解，但我不知道我能不能找到它。
为什么不是这样的呢?
//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++的解决方案。它在这里:
bool isRotation(string s1,string s2) {
string temp = s1;
temp += s1;
return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}
我喜欢检查s2是否是s1与s1连接的子字符串的答案。
我想要添加一个不会失去其优雅的优化。
你可以使用连接视图代替连接字符串(我不知道其他语言，但c++ Boost。Range提供这样的视图)。
由于检查一个字符串是否是另一个字符串的子字符串具有线性平均复杂度(最坏情况的复杂度是二次的)，这种优化应该平均提高2倍的速度。
纯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;
}
这是一个O(n) and in place算法。它对字符串的元素使用<操作符。当然不是我的。我把它从这里(网站是波兰语。我以前偶然发现过一次，现在在英语中找不到这样的东西，所以我展示了我拥有的:))。
bool equiv_cyc(const string &u, const string &v)
{
int n = u.length(), i = -1, j = -1, k;
if (n != v.length()) return false;
while( i<n-1 && j<n-1 )
{
k = 1;
while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
if (k>n) return true;
if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
}
return false;
}
我在Perl中这样做:
sub isRotation {
return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1;
}
使用strlen和strpos函数在PHP中很容易编写:
function isRotation($string1, $string2) {
return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}
我不知道strpos内部使用什么，但如果它使用KMP，它将在时间上是线性的。
现在来点完全不同的东西。
如果你想在一些约束条件下快速得到答案当字符串不是相互旋转时
在两个字符串上计算一些基于字符的校验和(比如xoring所有字符)。如果签名不同，字符串不是彼此的旋转。
同意，它可能会失败，但如果字符串不匹配，它会很快说，如果它们匹配，你仍然可以使用另一种算法，比如字符串连接来检查。
将每个字符作为振幅，并对其进行离散傅里叶变换。如果它们仅因旋转而不同，则频谱将在舍入误差范围内相同。当然，这是低效的，除非长度是2的幂，所以你可以做FFT:-)
反转其中一个字符串。取两者的FFT(将它们视为简单的整数序列)。将结果逐点相乘。使用反FFT转换回来。如果弦是彼此旋转的，那么结果将只有一个峰值——峰值的位置将由它们相对于彼此旋转的多少来指示。
