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

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

其他回答

当然,更好的答案应该是,“嗯,我会问stackoverflow社区,可能会在5分钟内得到至少4个非常好的答案”。有头脑是很好的,但我更看重那些知道如何与他人合作找到解决方案的人。

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

现在来点完全不同的东西。

如果你想在一些约束条件下快速得到答案当字符串不是相互旋转时

在两个字符串上计算一些基于字符的校验和(比如xoring所有字符)。如果签名不同,字符串不是彼此的旋转。

同意,它可能会失败,但如果字符串不匹配,它会很快说,如果它们匹配,你仍然可以使用另一种算法,比如字符串连接来检查。

为什么不是这样的呢?


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

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

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