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

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

例子:

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

"tackoverflows"
"ackoverflowst"
"overflowstack"

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

他给出的答案是:

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

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

提前谢谢你。


当前回答

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

其他回答

另一个基于答案的Ruby解决方案:

def rotation?(a, b); a.size == b.size and (b*2)[a]; end

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

另一个python示例(基于答案):

def isrotation(s1,s2):
     return len(s1)==len(s2) and s1 in 2*s2

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

由于其他人已经提交了二次最坏情况时间复杂度解决方案,我将添加一个线性解决方案(基于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;
}

工作示例