pythontip 100days-day3

Code › python
, ,

题目

给定两个字符串str1,str2判断str1是否是str2旋转后的字符串

例子

  • None,’hello’ -> False
  • None,None -> False
  • ‘’,’’ -> False
  • ‘hello’,’ehllo’-> False
  • ‘hello’,’llohe’ -> True

假设

  1. 字符串字符仅由ascii字符组成
  2. 大小写敏感

tips

  1. 枚举所有可能的旋转点并进行判断

代码

def is_rotation(s1, s2):
    pass

答案

此题有两种解法

解法1：

def is_rotation(s1, s2):
    if s1 is None or s2 is None:
        return False
    if len(s1) != len(s2):
        return False
    for i in range(0,len(s1)):
        if s1[:i + 1] == s2[-(i + 1):] and s1[i+1:] == s2[:len(s1) -i - 1]:
            return True
    return False

性能：

  1. 时间复杂度O(n^2)
  2. 空间复杂度O(1)

关键点：

  1. 如果s1由s2旋转而来，则一定存在一个位置作为分隔，使得s1的前段子串等于s2的后段子串，s1的后段子串等于s2的前段子串

解法2:

def is_rotation(s1, s2):
    if s1 is None or s2 is None:
        return False
    if len(s1) != len(s2):
        return False
    if s1 in s2 + s2:
        return True
    return False

性能：

  1. 时间复杂度O(n^2)
  2. 空间复杂度O(n)

关键点：

  1. 如果s1由s2旋转而来，s2 + s2 必然包含s1,例如 s1 = ‘hello’,s2 = ‘llohe’,s2 + s2 = ‘llohellohe’

解法3：

def is_rotation_find(s1, s2):
    if s1 is None or s2 is None:
        return False
    if len(s1) != len(s2):
        return False
    return True if (s1 + s1).find(s2) >= 0 else False

性能：

  1. 时间复杂度O(n^2)
  2. 空间复杂度O(n)

关键点：

  1. 思想和解法2一样，只是使用了find()方法，比解法2稍微麻烦一点。