Java 面试题：检查一根弦是否是另一根弦的旋转

Question

提问by Webdev

A friend of mine was asked the following question today at interview for the position of software developer:

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

Given two string s1and s2how will you check if s1is a rotatedversion of s2?

给定两个字符串s1，s2您将如何检查?s1的旋转版本s2？

Example:

例子：

If s1 = "stackoverflow"then the following are some of its rotated versions:

如果s1 = "stackoverflow"那么以下是它的一些旋转版本：

"tackoverflows"
"ackoverflowst"
"overflowstack"

where as "stackoverflwo"is nota rotated version.

其中，作为"stackoverflwo"是不旋转的版本。

The answer he gave was:

他给出的答案是：

Take s2and find the longest prefix that is a sub string of s1, that will give you the point of rotation. Once you find that point, break s2at that point to get s2aand s2b, then just check if concatenate(s2a,s2b) == s1

取s2，发现为子串最长前缀s1，这将使你的旋转点。一旦你找到那个点，s2在那个点中断以获得s2aand s2b，然后检查是否concatenate(s2a,s2b) == s1

It looks like a good solution to me and my friend. But the interviewer thought otherwise. He asked for a simpler solution. Please help me by telling how would you do this in Java/C/C++?

对我和我的朋友来说，这看起来是一个很好的解决方案。但面试官不这么认为。他要求一个更简单的解决方案。请帮助我告诉你如何做到这一点Java/C/C++？

Thanks in advance.

提前致谢。

Answer 1

采纳答案by codaddict

First make sure s1and s2are of the same length. Then check to see if s2is a substring of s1concatenated with s1:

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

In Java:

在 Java 中：

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

Answer 2

回答by Jon Skeet

EDIT: The accepted answer is clearly more elegant and efficient than this, if you spot it. I left this answer as what I'd do if I hadn't thought of doubling the original string.

编辑：如果你发现它，接受的答案显然比这更优雅和有效。如果我没有想到将原始字符串加倍，我将这个答案保留为我会做的事情。

I'd just brute-force it. Check the length first, and then try every possible rotation offset. If none of them work out, return false - if any of them does, return true immediately.

我只是蛮力它。首先检查长度，然后尝试每个可能的旋转偏移。如果它们都不起作用，则返回 false - 如果它们中的任何一个起作用，则立即返回 true。

There's no particular need to concatenate - just use pointers (C) or indexes (Java) and walk both along, one in each string - starting at the beginning of one string and the current candidate rotation offset in the second string, and wrapping where necessary. Check for character equality at each point in the string. If you get to the end of the first string, you're done.

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

It would probably be about as easy to concatenate - though probably less efficient, at least in Java.

连接起来可能很容易——尽管可能效率较低，至少在 Java 中是这样。

Answer 3

回答by Federico A. Ramponi

Another python example (based on THE answer):

另一个python示例（基于答案）：

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

Answer 4

回答by Opera

Fist, make sure the 2 strings have the same length. Then in C, you can do this with a simple pointer iteration.

拳头，确保两根弦的长度相同。然后在 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 == 'boolean isRotation(String s1, String s2) {
   return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\2\1");
}
')
            tmp2 = s2;
        }
      if (*tmp1 == 'boolean isRotation(String s1, String s2) {
   // neither string can contain "="
   return (s1 + "=" + s2).matches("(.*)(.*)=\2\1");
}
')
        return (1);
      else
        ++s2;
    }
  return (0);
}

Answer 5

回答by polygenelubricants

Here's one using regex just for fun:

这是一个使用正则表达式只是为了好玩：

boolean isRotation(String s1, String s2) {
   return (s1 + s2).matches(
      String.format("(.*)(.*)(?<=^.{%d})\2\1", s1.length())
   );
}

You can make it a bit simpler if you can use a special delimiter character guaranteed not to be in either strings.

如果您可以使用保证不在任一字符串中的特殊定界符，您可以使它更简单一些。

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

You can also use lookbehind with finite repetition instead:

您还可以使用带有有限重复的lookbehind：

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

Answer 6

回答by jpalecek

As others have submitted quadratic worst-case time complexity solution, I'd add a linear one (based on the KMP Algorithm):

由于其他人提交了二次最坏情况时间复杂度解决方案，我将添加一个线性解决方案（基于KMP 算法）：

static void Main(string[] args)
{
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "ztackoverflow"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "ackoverflowst"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "overflowstack"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "stackoverflwo"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "tackoverflwos"));
    Console.ReadLine();
}

public static bool IsRotation(string a, string b)
{
    Console.WriteLine("\nA: {0} B: {1}", a, b);

    if (b.Length != a.Length)
        return false;

    int ndx = a.IndexOf(b[0]);
    bool isRotation = true;
    Console.WriteLine("Ndx: {0}", ndx);
    if (ndx == -1) return false;
    for (int i = 0; i < b.Length; ++i)
    {
        int rotatedNdx = (i + ndx) % b.Length;
        char rotatedA = a[rotatedNdx];

        Console.WriteLine( "B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA );

        if (b[i] != rotatedA)
        {
            isRotation = false;
            // break; uncomment this when you remove the Console.WriteLine
        }
    }
    return isRotation;
}

working example

工作示例

Answer 7

回答by Chris Knight

Surely a better answer would be, "Well, I'd ask the stackoverflow community and would probably have at least 4 really good answers within 5 minutes". Brains are good and all, but I'd place a higher value on someone who knows how to work with others to get a solution.

当然，更好的答案是，“好吧，我会问 stackoverflow 社区，并且可能会在 5 分钟内得到至少 4 个非常好的答案”。大脑很好，但我更看重知道如何与他人合作以找到解决方案的人。

Answer 8

回答by RarrRarrRarr

Opera's simple pointer rotation trick works, but it is extremely inefficient in the worst case in running time. Simply imagine a string with many long repetitive runs of characters, ie:

Opera 的简单指针旋转技巧有效，但在运行时间最坏的情况下效率极低。简单地想象一个带有许多长重复字符的字符串，即：

S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2
S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

The "loop until there's a mismatch, then increment by one and try again" is a horrible approach, computationally.

“循环直到出现不匹配，然后递增一个并重试”在计算上是一种可怕的方法。

To prove that you can do the concatenation approach in plain C without too much effort, here is my solution:

为了证明您可以毫不费力地在普通 C 中执行连接方法，这是我的解决方案：

A: stackoverflow B: ztackoverflow
Ndx: -1
Rotation : False

A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
Rotation : False

A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
B: s A[0]: s
Rotation : False

This is linear in running time, at the expense of O(n) memory usage in overhead.

这在运行时间上是线性的，代价是 O(n) 内存使用开销。

(Note that the implementation of strstr() is platform-specific, but if particularly brain-dead, can always be replaced with a faster alternative such as the Boyer-Moore algorithm)

（请注意， strstr() 的实现是特定于平台的，但如果特别脑残，总是可以用更快的替代方法替换，例如 Boyer-Moore 算法）

Answer 9

回答by Michael Buen

Nobody offered a modulo approach yet, so here's one:

还没有人提供模数方法，所以这里有一个：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace TestRotate
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ztackoverflow"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ackoverflowst"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "overflowstack"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "stackoverflwo"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "tackoverflwos"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "owstackoverfl"));

            Console.ReadLine();
        }

        public static bool IsRotation(string a, string b)
        {
            Console.WriteLine("\nA: {0} B: {1}", a, b);

            if (b.Length != a.Length)
                return false;

            if (a.IndexOf(b[0]) == -1 )
                return false;

            foreach (int ndx in IndexList(a, b[0]))
            {
                bool isRotation = true;

                Console.WriteLine("Ndx: {0}", ndx);

                for (int i = 0; i < b.Length; ++i)
                {
                    int rotatedNdx = (i + ndx) % b.Length;
                    char rotatedA = a[rotatedNdx];

                    Console.WriteLine("B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA);

                    if (b[i] != rotatedA)
                    {
                        isRotation = false;
                        break;
                    }
                }
                if (isRotation)
                    return true;
            }
            return false;
        }

        public static IEnumerable<int> IndexList(string src, char c)
        {
            for (int i = 0; i < src.Length; ++i)
                if (src[i] == c)
                    yield return i;
        }

    }//class Program
}//namespace TestRotate

Output:

输出：

A: stackoverflow B: ztackoverflow
Rotation : False

A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A: stackoverflow B: owstackoverfl
Ndx: 5
B: o A[5]: o
B: w A[6]: v
Ndx: 11
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
Rotation : True

[EDIT: 2010-04-12]

[编辑：2010-04-12]

piotrnoticed the flaw in my code above. It errors when the first character in the string occurs twice or more. For example, stackoverflowtested against owstackoverflowresulted in false, when it should be true.

piotr注意到我上面代码中的缺陷。当字符串中的第一个字符出现两次或更多次时会出错。例如，stackoverflow测试owstackoverflow结果为 false，而它本应为 true。

Thanks piotr for spotting the error.

感谢 piotr 发现错误。

Now, here's the corrected code:

现在，这是更正后的代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IsRotation
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ztackoverflow"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ackoverflowst"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "overflowstack"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "stackoverflwo"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "owstackoverfl"));

            string strToTestFrom = "stackoverflow";
            foreach(string s in StringRotations(strToTestFrom))
            {
                Console.WriteLine("is {0} rotation of {1} ? {2}",
                    s, strToTestFrom,
                    IsRotation(strToTestFrom, s) );
            }
            Console.ReadLine();
        }

        public static IEnumerable<string> StringRotations(string src)
        {
            for (int i = 0; i < src.Length; ++i)
            {
                var sb = new StringBuilder();
                for (int x = 0; x < src.Length; ++x)
                    sb.Append(src[(i + x) % src.Length]);

                yield return sb.ToString();
            }
        }

        public static bool IsRotation(string a, string b)
        {
            if (b.Length != a.Length || a.IndexOf(b[0]) < 0 ) return false;
            foreach(int ndx in IndexList(a, b[0]))
            {
                int i = ndx;
                if (b.ToCharArray().All(x => x == a[i++ % a.Length]))
                    return true;
            }
            return false;
        }

        public static IEnumerable<int> IndexList(string src, char c)
        {
            for (int i = 0; i < src.Length; ++i)
                if (src[i] == c)
                    yield return i;
        }

    }//class Program

}//namespace IsRotation

Here's the output:

这是输出：

Rotation : False
Rotation : True
Rotation : True
Rotation : False
Rotation : True
is stackoverflow rotation of stackoverflow ? True
is tackoverflows rotation of stackoverflow ? True
is ackoverflowst rotation of stackoverflow ? True
is ckoverflowsta rotation of stackoverflow ? True
is koverflowstac rotation of stackoverflow ? True
is overflowstack rotation of stackoverflow ? True
is verflowstacko rotation of stackoverflow ? True
is erflowstackov rotation of stackoverflow ? True
is rflowstackove rotation of stackoverflow ? True
is flowstackover rotation of stackoverflow ? True
is lowstackoverf rotation of stackoverflow ? True
is owstackoverfl rotation of stackoverflow ? True
is wstackoverflo rotation of stackoverflow ? True

Here's the lambda approach:

这是 lambda 方法：

int rotation(char *s1,char *s2)
{
    int i,j,k,p=0,n;
    n=strlen(s1);
    k=strlen(s2);
    if (n!=k)
        return 0;
    for (i=0;i<n;i++)
    {
        if (s1[0]==s2[i])
        {
            for (j=i,k=0;k<n;k++,j++)
            {
                if (s1[k]==s2[j])
                    p++;
                if (j==n-1)
                    j=0;
            }
        }
    }
    if (n==p+1)
      return 1;
    else
      return 0;
}

Here's the lambda approach output:

这是 lambda 方法的输出：

##代码##

Answer 10

回答by mannrecaged

##代码##

Java 面试题：检查一根弦是否是另一根弦的旋转

提问by Webdev

采纳答案by codaddict

回答by Jon Skeet

回答by Federico A. Ramponi

回答by Opera

回答by polygenelubricants

回答by jpalecek

回答by Chris Knight

回答by RarrRarrRarr

回答by Michael Buen

回答by mannrecaged

相关推荐

最近更新

标签

Java 面试题：检查一根弦是否是另一根弦的旋转

提问by Webdev

采纳答案by codaddict

回答by Jon Skeet

回答by Federico A. Ramponi

回答by Opera

回答by polygenelubricants

回答by jpalecek

回答by Chris Knight

回答by RarrRarrRarr

回答by Michael Buen

回答by mannrecaged

相关推荐

Java 流到新集合的集合

Java：将科学记数法转换为常规 int

Java 中的 Unicode 转义语法

从 Java 应用程序即时打开 PDF 文件

相关推荐

最近更新

标签