题目0796:旋转字符串

题目描述

给定两个字符串,A和B。

A的旋转操作就是将A最左边的字符移动到最右边。例如,若A='abcde',在移动一次之后结果就是'bcdea'。如果在若干次旋转操作之后,A能变成B,那么返回True。

示例1:

输入: A = 'abcde', B = 'cdeab'
输出: true

示例2:

输入: A = 'abcde', B = 'abced'
输出: false

注意:

A和B长度不超过100。

解答技巧

• 方法一:穷举法

将字符串A旋转s次后,得到的字符串为A[s],A[s + 1],A[s + 2],...,因此我们只要枚举s,并检查是否有A[s]==B[0],A[s+1]==B[1],A[s+2]==B[2], ... 即可。

class Solution(object):
    def rotateString(self, A, B):
        if len(A) != len(B):
            return False
        if len(A) == 0:
            return True

        for s in xrange(len(A)):
            if all(A[(s+i) % len(A)] == B[i] for i in xrange(len(A))):
                return True
        return False

复杂度分析:

时间复杂度:$O(N^2)$,其中$N$是字符串A的长度。

空间复杂度:$O(1)$。

• 方法二：判断子串

由于A+A包含了所有可以通过旋转操作从A得到的字符串,因此我们只需要判断B是否为A+A的子串即可。

class Solution(object):
    def rotateString(self, A, B):
        return len(A) == len(B) and B in A+A

复杂度分析:

时间复杂度:$O(N^2)$,其中$N$是字符串A的长度。

空间复杂度:$O(N)$,即A+A需要的空间。

• 方法三:Rabin-Karp字符串哈希

我们可以优化方法二中判断B是否为A+A的子串时使用的算法,例如使用Rabin-Karp字符串哈希算法。设A2=A+A,我们求出子串A2[0:N],A2[1:N+1],A2[2:N+2],...的哈希值,如果与B的哈希值相同,那么这两个字符串很有可能相同。

我们通过hash(S)=(S[0] * P**0 + S[1] * P**1 + S[2] * P**2 + ...) % MOD计算字符串S的哈希值,其中S[i]是 S 中第i个字母的ASCII编码值,X**Y表示指数运算。对于两个字符串S和T,如果它们的哈希值相同,即hash(S)==hash(T),那么S和T很有可能相同。

当我们计算出A的哈希值hash(A)(即为序列A[0],A[1],...,A[N - 1]的哈希值),下一步是计算A经过一次旋转操作,序列A[1], A[2],...,A[N - 1],A[0]的哈希值,这可以通过将hash(A)减去A[0],除以P,再加上A[0] * P**(N - 1)得到。其中除以P的操作是在对MOD取模的意义下的,等价于乘以P的乘法逆元。如果MOD为质数,P的乘法逆元Pinv为P**(MOD - 2)对MOD取模的结果。这可以根据费马小定理推导出。

class Solution(object):
    def rotateString(self, A, B):
        MOD = 10**9 + 7
        P = 113
        Pinv = pow(P, MOD-2, MOD)

        hb = 0
        power = 1
        for x in B:
            code = ord(x) - 96
            hb = (hb + power * code) % MOD
            power = power * P % MOD

        ha = 0
        power = 1
        for x in A:
            code = ord(x) - 96
            ha = (ha + power * code) % MOD
            power = power * P % MOD

        if ha == hb and A == B: return True
        for i, x in enumerate(A):
            code = ord(x) - 96
            ha += power * code
            ha -= code
            ha *= Pinv
            ha %= MOD
            if ha == hb and A[i+1:] + A[:i+1] == B:
                return True
        return False

复杂度分析:

时间复杂度:$O(N)$,其中$N$是字符串A的长度。

空间复杂度:$O(N)$。

• 方法四:KMP算法

判断一个串是否为另一个串的子串的最优时间复杂度的算法是KMP算法。和方法二相同,我们只需要用KMP算法判断B是否为A+A的子串即可。KMP算法较难理解,这里给出了力扣第28题实现strstr()讨论区中一个高赞KMP算法详解,以及著名博主Matrix67的KMP 算法详解。

class Solution:
    def rotateString(self, A, B):
        N = len(A)
        if N != len(B): return False
        if N == 0: return True

        #Compute shift table
        shifts = [1] * (N+1)
        left = -1
        for right in xrange(N):
            while left >= 0 and B[left] != B[right]:
                left -= shifts[left]
            shifts[right + 1] = right - left
            left += 1

        #Find match of B in A+A
        match_len = 0
        for char in A+A:
            while match_len >= 0 and B[match_len] != char:
                match_len -= shifts[match_len]

            match_len += 1
            if match_len == N:
                return True

        return False

复杂度分析:

时间复杂度:$O(N)$,其中$N$是字符串A的长度。

空间复杂度:$O(N)$。