我的一位朋友今天在面试中被问到以下问题:软件开发人员的职位:
鉴于两个字符串s1,s2您将如何检查是否s1是旋转版本s2？
例:
如果s1 = "stackoverflow"那么以下是它的一些旋转版本:
"tackoverflows"
"ackoverflowst"
"overflowstack"
其中,作为"stackoverflwo"是不旋转的版本.
他给出的答案是:
获取
s2并找到作为子字符串的最长前缀,s1它将为您提供旋转点.一旦你找到那个点,突破s2该点处得到s2a和s2b,然后就检查concatenate(s2a,s2b) == s1
对我和我的朋友来说,这似乎是一个很好的解决方案.但面试官不这么认为.他要求一个更简单的解决方案.请告诉我你将如何做到这一点来帮助我Java/C/C++？
提前致谢.
cod*_*ict 687
首先确保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);
}
Chr*_*ght 101
当然,一个更好的答案是,"好吧,我会问堆栈流社区,并且可能在5分钟内至少有4个非常好的答案".大脑是好的,但是我会更加重视那些知道如何与他人合作以获得解决方案的人.
Fed*_*oni 49
另一个python示例(基于THE答案):
def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
jpa*_*cek 32
由于其他人提交了二次最坏情况时间复杂度解决方案,我会添加一个线性的(基于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;
}
Jon*_*eet 25
编辑:如果你发现,接受的答案显然比这更优雅和有效.如果我没有想到将原始字符串加倍,我就把这个答案留给了我.
我只是暴力强迫它.首先检查长度,然后尝试每个可能的旋转偏移.如果它们都没有成功,则返回false - 如果其中任何一个成功,则立即返回true.
没有特别需要连接 - 只需使用指针(C)或索引(Java)并同时走,每个字符串一个 - 从一个字符串的开头开始,第二个字符串中的当前候选旋转偏移量,并在必要时包装.检查字符串中每个点的字符相等性.如果你到达第一个字符串的末尾,那就完成了.
它可能很容易连接 - 尽管可能效率较低,至少在Java中是这样.
pol*_*nts 17
这是一个使用正则表达式只是为了好玩:
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");
}
您也可以使用有限重复的lookbehind:
boolean isRotation(String s1, String s2) {
return (s1 + s2).matches(
String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
);
}
use*_*691 10
哇,哇......为什么每个人都对O(n^2)答案如此激动？我很肯定我们可以在这里做得更好.上面的答案包括循环中的O(n)操作O(n)(substring/indexOf调用).即使使用更有效的搜索算法; 说Boyer-Moore或者KMP,最糟糕的情况仍然O(n^2)是重复.
一个O(n)随机的答案是简单的; 采用支持O(1)滑动窗口的哈希(如拉宾指纹); 哈希字符串1,然后哈希字符串2,继续在字符串周围移动哈希1的窗口,看看哈希函数是否冲突.
如果我们想象最糟糕的情况就像是"扫描两股DNA",那么碰撞的概率就会上升,这可能会退化为某种类似的O(n^(1+e))东西(只是在这里猜测).
最后,有一个确定性的O(nlogn)解决方案,外面有一个非常大的常数.基本上,这个想法是对两个字符串进行卷积.卷积的最大值将是旋转差(如果它们被旋转); 一O(n)检查确认.好的是,如果有两个相等的最大值,那么它们都是有效的解决方案.您可以使用两个FFT和一个点积以及一个iFFT进行卷积nlogn + nlogn + n + nlogn + n == O(nlogn).
由于你不能用零填充,并且你不能保证字符串长度为2 ^ n,因此FFT不会是快速的; 它们将是缓慢的,O(nlogn)但仍然是比CT算法更大的常数.
所有这一切,我绝对是100%肯定的,这里有一个确定性的O(n)解决方案,但是如果我能找到它就会变得愚蠢.
小智 8
拳头,确保2个琴弦长度相同.然后在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);
}
这是一个O(n)和现在的alghoritm.它使用<运算符作为字符串的元素.当然不是我的.我从这里拿了它(这个网站很流行.我曾经偶然发现过一次,我现在用英语找不到那样的东西,所以我展示了我的东西:)).
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;
}
我想这样做更好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/;
}
甚至更好地使用索引函数而不是正则表达式:
sub isRotation {
my($string1,$string2) = @_;
return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}
不确定这是否是最有效的方法,但它可能相对有趣:Burrows-Wheeler变换.根据WP的文章,输入的所有旋转产生相同的输出.对于诸如压缩之类的应用,这是不可取的,因此指示原始旋转(例如通过索引;参见文章).但对于简单的旋转独立比较,它听起来很理想.当然,它不一定非常有效!
还没有人提供模数方法,所以这里有一个:
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注意到我上面代码中的缺陷.当字符串中的第一个字符出现两次或更多时,它会出错.例如,当它应该是真的时,stackoverflow测试反对owstackoverflow导致错误.
感谢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