CTCI第6版1.9

Question

问题：检查s2是否是s1的旋转。你知道吗

def check(s1, s2):

  s1 += s1
  return (s1.find(s2) != -1)

s1 = 'abcd'
s2 = 'dabc'
print(check(s1, s2))

METHOD 2

def check(s1, s2):

  s1 = list(s1)
  s2 = list(s2)

  for _ in range (len(s2)):
    if s1 != s2:
      curr = s2.pop()
      s2.insert(0,curr)
    else:
      return True
  return False

s1 = 'abcd'
s2 = 'dabc'
print(check(s1, s2))

我想比较这两个工作和完成的解决方案，都运行在O（N）时间，但我不确定的空间复杂性。你知道吗

对于第一个，有一个字符串附加，所以它需要O（N）空间与s1的长度成比例？ 在第二种情况下，两个数组创建的O（Len（s1）+Len（s2））空间？你知道吗

谢谢

Answer 1

In [15]: s1 = 'abcd' 
    ...: s2 = 'dabc'                                                                                                                                                                          

In [16]: set(s1).difference(set(s2))                                                                                                                                                          
Out[16]: set()


In [23]: s1 = 'abcder' 
    ...: s2 = 'dabc'                                                                                                                                                                          

In [24]: set(s1).difference(set(s2))                                                                                                                                                          
Out[24]: {'e', 'r'}

你可以用集合来求解：https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset

示例：

def check(s1, s2): 
    return not set(s1).symmetric_difference(set(s2)) and len(s1) == len(s2)