检查字符串是否是另一个字符串的旋转而不连接

Question

有两个字符串,我们如何检查一个是否是另一个的旋转版本？

For Example : hello --- lohel

一个简单的解决方案是concatenating首先使用自身的字符串并检查另一个是否是substring连接版本的字符串.

还有其他解决方案吗？

我想知道我们是否可以使用它circular linked list？但我无法达成解决方案.

Answer 1

一个简单的解决方案是通过连接它们并检查另一个是否是连接版本的子字符串.

我假设你的意思是连接第一个字符串与自身,然​​后检查另一个字符串是否是该连接的子字符串.

这将起作用,事实上可以在没有任何连接的情况下完成.只需使用任何字符串搜索算法在第一个字符串中搜索第二个字符串,当您到达结尾时,循环回到开头.

例如,使用Boyer-Moore,整体算法将是O(n).

Answer 2

根本不需要连接.

首先,检查长度.如果它们不同则返回false.

其次,使用从第一个字符到最后一个字符递增的索引.检查目的地是否以索引到结尾的所有字母开头,并以索引前的所有字母结束.如果在任何时候这是真的,则返回true.

否则,返回false.

编辑:

Python中的实现:

def isrot(src, dest):
  # Make sure they have the same size
  if len(src) != len(dest):
    return False

  # Rotate through the letters in src
  for ix in range(len(src)):
    # Compare the end of src with the beginning of dest
    # and the beginning of src with the end of dest
    if dest.startswith(src[ix:]) and dest.endswith(src[:ix]):
      return True

  return False

print isrot('hello', 'lohel')
print isrot('hello', 'lohell')
print isrot('hello', 'hello')
print isrot('hello', 'lohe')