原文链接: https://leetcode-cn.com/problems/rotate-string

英文原文

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

• For example, if s = "abcde", then it will be "bcdea" after one shift.

 

Example 1:

Input: s = "abcde", goal = "cdeab"
Output: true

Example 2:

Input: s = "abcde", goal = "abced"
Output: false

 

Constraints:

• 1 <= s.length, goal.length <= 100
• s and goal consist of lowercase English letters.

中文题目

给定两个字符串, 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], ... 即可。

[sol1]
class Solution {
    public boolean rotateString(String A, String B) {
        if (A.length() != B.length())
            return false;
        if (A.length() == 0)
            return true;

        search:
            for (int s = 0; s < A.length(); ++s) {
                for (int i = 0; i < A.length(); ++i) {
                    if (A.charAt((s+i) % A.length()) != B.charAt(i))
                        continue search;
                }
                return true;
            }
        return false;
    }
}

[sol1]
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 的子串即可。

[sol2]
class Solution {
    public boolean rotateString(String A, String B) {
        return A.length() == B.length() && (A + A).contains(B);
    }
}

[sol2]
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 取模的结果。这可以根据费马小定理推导出。

[sol3]
import java.math.BigInteger;
class Solution {
    public boolean rotateString(String A, String B) {
        if (A.equals(B)) return true;

        int MOD = 1_000_000_007;
        int P = 113;
        int Pinv = BigInteger.valueOf(P).modInverse(BigInteger.valueOf(MOD)).intValue();

        long hb = 0, power = 1;
        for (char x: B.toCharArray()) {
            hb = (hb + power * x) % MOD;
            power = power * P % MOD;
        }

        long ha = 0; power = 1;
        char[] ca = A.toCharArray();
        for (char x: ca) {
            ha = (ha + power * x) % MOD;
            power = power * P % MOD;
        }

        for (int i = 0; i < ca.length; ++i) {
            char x = ca[i];
            ha += power * x - x;
            ha %= MOD;
            ha *= Pinv;
            ha %= MOD;
            if (ha == hb && (A.substring(i+1) + A.substring(0, i+1)).equals(B))
                return true;

        }
        return false;
    }
}

[sol3]
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 算法详解。

[sol4]
class Solution {
    public boolean rotateString(String A, String B) {
        int N = A.length();
        if (N != B.length()) return false;
        if (N == 0) return true;

        //Compute shift table
        int[] shifts = new int[N+1];
        Arrays.fill(shifts, 1);
        int left = -1;
        for (int right = 0; right < N; ++right) {
            while (left >= 0 && (B.charAt(left) != B.charAt(right)))
                left -= shifts[left];
            shifts[right + 1] = right - left++;
        }

        //Find match of B in A+A
        int matchLen = 0;
        for (char c: (A+A).toCharArray()) {
            while (matchLen >= 0 && B.charAt(matchLen) != c)
                matchLen -= shifts[matchLen];
            if (++matchLen == N) return true;
        }

        return false;
    }
}

[sol4]
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)$。

统计信息

通过次数	提交次数	AC比率
25413	47326	53.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言