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

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

例子:

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

"tackoverflows"
"ackoverflowst"
"overflowstack"

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

他给出的答案是:

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

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

提前谢谢你。


当前回答

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

其他回答

首先,确保两根弦的长度相同。然后在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);
}

编辑:如果你发现了,公认的答案显然比这个更优雅、更有效。我把这个答案留给了我所做的,如果我没有想到将原始字符串加倍的话。


我就用蛮力。首先检查长度,然后尝试每一个可能的旋转偏移。如果没有,则返回false;如果有,则立即返回true。

没有特别的连接需要——只需使用指针(C)或索引(Java),并在每个字符串中使用一个指针——从一个字符串的开头开始,在第二个字符串中使用当前的候选旋转偏移量,并在必要的地方进行换行。检查字符串中每个点的字符是否相等。如果你到达了第一个字符串的末尾,你就完成了。

它可能同样容易连接-尽管效率可能较低,至少在Java中是这样。

下面是一个使用正则表达式的例子,只是为了好玩:

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

Opera的简单指针旋转技巧是有效的,但是在运行时最糟糕的情况下效率极低。简单地想象一个有许多长重复字符的字符串,例如:

S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2 S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

从计算角度来看,“循环直到出现不匹配,然后再加1,再试一次”是一种可怕的方法。

为了证明你可以毫不费力地在C语言中使用串联方法,下面是我的解决方案:

  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-Moore算法)

将每个字符作为振幅,并对其进行离散傅里叶变换。如果它们仅因旋转而不同,则频谱将在舍入误差范围内相同。当然,这是低效的,除非长度是2的幂,所以你可以做FFT:-)