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

给定两个字符串s1和s2,你将如何检查s1是否是s2的旋转版本?

例子:

如果s1 = "stackoverflow",则以下是它的一些旋转版本:

"tackoverflows"
"ackoverflowst"
"overflowstack"

其中“stackoverflwo”不是一个旋转的版本。

他给出的答案是:

取s2,找出s1的子字符串中最长的前缀,就能得到旋转的点。一旦你找到了那个点,在那个点打断s2得到s2a和s2b,然后检查是否连接(s2a,s2b) == s1

对我和我的朋友来说,这是一个很好的解决方案。但是面试官不这么认为。他要求一个更简单的解决办法。请告诉我在Java/C/ c++中你是如何做到这一点的?

提前谢谢你。


当前回答

反转其中一个字符串。取两者的FFT(将它们视为简单的整数序列)。将结果逐点相乘。使用反FFT转换回来。如果弦是彼此旋转的,那么结果将只有一个峰值——峰值的位置将由它们相对于彼此旋转的多少来指示。

其他回答

为什么不是这样的呢?


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

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

不确定这是否是最有效的方法,但它可能相对有趣:Burrows-Wheeler变换。根据WP文章,输入的所有旋转产生相同的输出。对于压缩等应用程序,这是不可取的,所以原始旋转被指示(例如通过索引;参见文章)。但对于简单的与旋转无关的比较,这听起来很理想。当然,这并不一定是理想的效率!

首先确保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);
}

哇,哇……为什么每个人都对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)解,但我不知道我能不能找到它。

这是一个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;
}