今天，我的一个朋友在面试软件开发人员的职位时被问到以下问题:
给定两个字符串s1和s2，你将如何检查s1是否是s2的旋转版本?
例子:
如果s1 = "stackoverflow"，则以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中“stackoverflwo”不是一个旋转的版本。
他给出的答案是:
取s2，找出s1的子字符串中最长的前缀，就能得到旋转的点。一旦你找到了那个点，在那个点打断s2得到s2a和s2b，然后检查是否连接(s2a,s2b) == s1
对我和我的朋友来说，这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?
提前谢谢你。
当前回答
下面是一个使用正则表达式的例子，只是为了好玩:
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())
);
}
其他回答
因为没有人给出c++的解决方案。它在这里:
bool isRotation(string s1,string s2) {
string temp = s1;
temp += s1;
return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}
另一个基于答案的Ruby解决方案:
def rotation?(a, b); a.size == b.size and (b*2)[a]; end
纯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;
}
首先确保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);
}
为什么不是这样的呢?
//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;
}
编辑:我可能会有一些差一的问题;我不想检查。；）
