面试问题：检查一个string是否是其他string的旋转

我的一位朋友今天在面试时被问到了软件开发人员的职位：

给定两个strings1和s2你将如何检查s1是否是s2的旋转版本？

例：

如果s1 = "stackoverflow"那么下面是它的一些旋转版本：

 "tackoverflows" "ackoverflowst" "overflowstack" 

作为"stackoverflwo" 不是一个旋转的版本。

他给出的答案是：

以s2为例，find最长的s1子string前缀，这会给你一个旋转点。 一旦你find了这一点，在这一点上打破s2来获得s2a和s2b ，然后检查是否concatenate(s2a,s2b) == s1

这对我和我的朋友来说是一个很好的解决scheme。 但面试官认为不然。 他要求一个更简单的解决scheme。 请告诉我如何在Java/C/C++做到这一点？

提前致谢。

Answer 1

首先确保s1和s2的长度相同。 然后检查s2是否与s1连接的s1的子string：

 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); } 

Answer 2

当然，更好的答案是，“我会问stackoverflow社区，并可能在5分钟内至less有4个非常好的答案”。 大脑是好的，但是我会把一个更高的价值放在一个知道如何与他人合作来获得解决scheme的人身上。

Answer 3

另一个python的例子（基于答案）：

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

Answer 4

由于其他人已经提交了二次最坏情况时间复杂度解决scheme，我会添加一个线性（基于KMPalgorithm ）：

 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; } 

工作示例

Answer 5

编辑：接受的答案显然比这更优雅和高效，如果你发现它。 我留下了这个答案，因为如果我没有想到将原始string加倍，我会这样做。

---

我只是蛮横的。 首先检查长度，然后尝试每个可能的旋转偏移量。 如果它们中没有一个成功，则返回false – 如果其中任何一个返回true，则立即返回true。

没有特别的需要连接 – 只需使用指针（C）或索引（Java），并沿着每一个string走一个，从一个string的开始处开始，并在第二个string中当前的候选旋转偏移量，并在必要时包装。 检查string中每个点的字符是否相等。 如果你到了第一个string的末尾，你就完成了。

这可能是简单的连接 – 尽pipe可能效率较低，至less在Java中。

Answer 6

这里使用正则expression式只是为了好玩：

 boolean isRotation(String s1, String s2) { return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1"); } 

如果你可以使用一个特殊的分隔符保证不在任何string中，你可以使它更简单一些。

 boolean isRotation(String s1, String s2) { // neither string can contain "=" return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1"); } 

你也可以用有限重复的lookbehind来代替：

 boolean isRotation(String s1, String s2) { return (s1 + s2).matches( String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length()) ); } 

Answer 7

哇，哇…为什么每个人都对O(n^2)答案如此激动呢？ 我确信我们可以在这里做得更好。 上面的答案包括O(n)循环（substring / indexOf调用）中的O(n)操作。 即使使用更高效的searchalgorithm， 说Boyer-Moore或者KMP ，最坏的情况还是O(n^2)有重复。

一个O(n)随机答案是直接的; 采取哈希（如拉宾指纹），支持一个O(1)滑动窗口; 散列string1，然后散列string2，然后继续移动散列1的窗口围绕string，看散列函数是否发生冲突。

如果我们想象最糟糕的情况就像是“扫描两股DNA”，那么碰撞的可能性就会上升，而这可能会退化成O(n^(1+e))东西（这里只是猜测）。

最后，还有一个确定性的O(nlogn)解决scheme，在外面有一个非常大的常数。 基本上，这个想法是对两个string进行卷积。 卷积的最大值将是旋转差（如果旋转）; O(n)检查确认。 好的是，如果有两个相等的最大值，那么它们都是有效的解决scheme。 你可以用两个FFT和一个点积和一个iFFT进行卷积，所以nlogn + nlogn + n + nlogn + n == O(nlogn) 。

既然你不能填零，而且你不能保证string的长度是2 ^ n，那么FFT将不会是快的; 它们将是慢速的，仍然是O(nlogn)但比CTalgorithm大得多。

所有这一切，我绝对100％肯定地说，在这里有一个确定性的O(n)解决scheme，但是如果我能find它的话，我也会感到厌倦。

Answer 8

拳头，确保2个string具有相同的长度。 然后在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); } 

Answer 9

这是一个O(n)和alghoritm。 它使用<运算符作为string的元素。 当然不是我的。 我把它从这里拿出来 （这个网站很好，我曾经偶然发现过，现在用英文找不到这样的东西，所以我展示了我的:)）。

 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; } 

Answer 10

我猜在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/; } 

或者更好的使用索引函数而不是正则expression式：

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

Answer 11

不知道这是否是最有效的方法，但可能相对有趣 ： Burrows-Wheeler转换 。 根据WP文章，input的所有旋转产生相同的输出。 对于诸如压缩之类的应用，这是不可取的，所以原始的旋转被指示（例如通过索引;参见文章）。 但是对于简单的旋转独立比较来说，这听起来很理想。 当然，这不一定是理想的效率！

Answer 12

把每个字符作为一个幅度，并对它们进行离散傅里叶变换。 如果它们仅通过旋转而不同，则频谱将在舍入误差内相同。 当然，这是效率低下，除非长度是2的幂，所以你可以做一个FFT 🙂

Answer 13

目前还没有人提供模数方法，所以这里是一个：

 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注意到我的代码上面的缺陷。 当string中的第一个字符出现两次或更多时出错。 例如，对于owstackoverflowtesting的stackoverflow导致错误，当它应该是真实的。

感谢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 

Answer 14

因为没有人提供过C ++解决scheme。 在这里它：

 bool isRotation(string s1,string s2) { string temp = s1; temp += s1; return (s1.length() == s2.length()) && (temp.find(s2) != string::npos); } 

Answer 15

Opera的简单的指针旋转技巧是有效的，但是在最坏的情况下，它在运行时间效率极低。 简单地想象一个string，它有很多重复的字符，比如：

S1 = HELLOHELLOHELLHELLOHELLOHELLO2

S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

“循环直到有一个不匹配，然后再增加一个，再试一次”是一个可怕的方法，在计算上。

为了certificate你可以用简单的C语言来完成连接方法，这里是我的解决scheme：

  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-Moorealgorithm等更快的替代方法替代）

Answer 16

C＃：

 s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2) 

Answer 17

我喜欢检查s2是否与s1串联的s1的子串的答案。

我想添加一个不失优雅的优化。

而不是连接string，你可以使用连接视图（我不知道其他语言，但为C ++ Boost.Range提供这样的意见）。

由于检查一个string是否是另一个string的子string具有线性平均复杂度（最坏情况复杂度是二次的），所以这个优化应该平均提高速度2倍。

Answer 18

一个纯粹的Java答案（sans null检查）

 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; } 

Answer 19

而现在完全不同的东西。

如果你想在一些受约束的情况下非常快速的回答，当string不是彼此旋转

• 计算两个string上的一些基于字符的校验和（如xoring所有字符）。 如果签名不同，string不是彼此旋转。

同意，它可能会失败，但是如果string不匹配，并且如果它们匹配，则仍然可以使用string连接等其他algorithm来检查。

Answer 20

另一个基于答案的Ruby解决scheme：

 def rotation?(a, b); a.size == b.size and (b*2)[a]; end 

Answer 21

使用strlen和strpos函数编写PHP非常容易：

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

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

Answer 22

反转其中一个string。 以两者的FFT（将它们视为简单的整数序列）。 将这些结果叠加在一起。 使用逆FFT进行变换。 如果弦是彼此旋转的，结果将会有一个单峰 – 峰的位置将表示它们相对于彼此旋转了多less。

Answer 23

为什么不是这样的？

 //is qa 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; } 

编辑：我可能有一些脱节的问题; 不想检查。 ;）

Answer 24

我会在Perl中这样做：

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

Answer 25

 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; } 

Answer 26

用string2joinstring1 ，用KMPalgorithm检查string2是否出现在新形成的string中。 由于KMP的时间复杂度小于substr 。