跳至主要內容

0796. 旋转字符串

ITCharge大约 2 分钟

0796. 旋转字符串open in new window

  • 标签:字符串、字符串匹配
  • 难度:简单

题目链接

题目大意

描述:给定两个字符串 sgoal

要求:如果 s 在若干次旋转之后,能变为 goal,则返回 True,否则返回 False

说明

  • s 的旋转操作:将 s 最左侧的字符移动到最右边。
    • 比如:s = "abcde",在旋转一次之后结果就是 s = "bcdea"
  • 1s.length,goal.length1001 \le s.length, goal.length \le 100
  • sgoal 由小写英文字母组成。

示例

  • 示例 1:
输入: s = "abcde", goal = "cdeab"
输出: true
  • 示例 2:
输入: s = "abcde", goal = "abced"
输出: false

解题思路

思路 1:KMP 算法

其实将两个字符串 s 拼接在一起,就包含了所有从 s 进行旋转后的字符串。那么我们只需要判断一下 goal 是否为 s + s 的子串即可。可以用 KMP 算法来做。

  1. 先排除掉几种不可能的情况,比如 s 为空串的情况,goal 为空串的情况,len(s) != len(goal) 的情况。
  2. 然后使用 KMP 算法计算出 goals + s 中的下标位置 indexs + s 可用取余运算模拟)。
  3. 如果 index == -1,则说明 s 在若干次旋转之后,不能能变为 goal,则返回 False
  4. 如果 index != -1,则说明 s 在若干次旋转之后,能变为 goal,则返回 True

思路 1:代码

class Solution:
    def kmp(self, T: str, p: str) -> int:
        n, m = len(T), len(p)

        next = self.generateNext(p)

        i, j = 0, 0
        while i - j < n:
            while j > 0 and T[i % n] != p[j]:
                j = next[j - 1]
            if T[i % n] == p[j]:
                j += 1
            if j == m:
                return i - m + 1
            i += 1
        return -1

    def generateNext(self, p: str):
        m = len(p)
        next = [0 for _ in range(m)]

        left = 0
        for right in range(1, m):
            while left > 0 and p[left] != p[right]:
                left = next[left - 1]
            if p[left] == p[right]:
                left += 1
            next[right] = left

        return next

    def rotateString(self, s: str, goal: str) -> bool:
        if not s or not goal or len(s) != len(goal):
            return False
        index = self.kmp(s, goal)
        if index == -1:
            return False
        return True

思路 1:复杂度分析

  • 时间复杂度O(n+m)O(n + m),其中文本串 ss 的长度为 nn,模式串 goalgoal 的长度为 mm
  • 空间复杂度O(m)O(m)