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

给定两个字符串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);
}

其他回答

C#:

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

首先确保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中是这样。

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

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

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

为什么不是这样的呢?


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

编辑:我可能会有一些差一的问题;我不想检查。;)