LeetCode 796. 旋转字符串

约 3 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 5-10 腾讯 字节 华为 美团 快手
标签
字符串 字符串匹配

题目描述

✅ 796. 旋转字符串

image-20260928235605463

题意分析

每次把 s 的第一个字符移到末尾，判断重复若干次后能否得到 goal，允许零次操作。旋转不会改变长度，也不会改变字符绕成一圈后的先后顺序。

长度为 n 的字符串旋转 n 次就回到原串，因此只需考虑从各个位置开始读取一整圈的结果。

解法：拼接字符串判断子串

核心思路

[!blue]

把原串在位置 k 分成前缀 s[0:k] 和后缀 s[k:n]。左移 k 次后的结果就是 s[k:n] + s[0:k]：先读后缀，再接回前缀。

在 s + s 中，从位置 k 开始读取 n 个字符，恰好也是这两部分。因此每一种旋转结果都在双倍串中连续出现，不必逐次移动字符。

反过来，只要 goal 长度也是 n，它在双倍串中的一次完整匹配就对应这样的切分。若匹配从位置 n 开始，读到的是第二份原串，等价于零次旋转。所以“长度相同，并且是 s + s 的子串”既是必要条件，也是充分条件。

解题步骤

  1. 比较 s 和 goal 的长度，不同则直接返回 false，无需拼接。
  2. 构造 s + s，让跨越原串末尾的旋转结果变成连续子串。
  3. 调用标准库的子串查找，找到就返回 true，否则返回 false。原串自身已经包含在双倍串中，不需要单独处理零次旋转。

代码实现

class Solution {
    public boolean rotateString(String s, String goal) {
        // 长度不相等不可能通过旋转得到，先排除短片段误匹配
        if (s.length() != goal.length()) {
            return false;
        }

        // 等长目标在双倍串中的一次匹配，对应环绕一整圈
        return (s + s).contains(goal);
    }
}

import "strings"

func rotateString(s string, goal string) bool {
    // 长度不相等不可能通过旋转得到，先排除短片段误匹配
    if len(s) != len(goal) {
        return false
    }
    // 等长目标在双倍串中的一次匹配，对应环绕一整圈
    return strings.Contains(s+s, goal)
}

复杂度分析

  • 时间复杂度：拼接 $O(n)$；子串查找代价依赖标准库实现，按朴素匹配估算上界为 $O(n^2)$。
  • 空间复杂度：$O(n)$，保存双倍字符串。

关键点总结

[!green]

  • 长度相同保证匹配片段恰好覆盖一整圈。
  • 原串自身对应零次旋转。

易错点总结

[!yellow]

  • 省略长度检查会把较短片段误当成完整旋转结果。
  • 只比较字符计数，无法保证环形次序。
  • 把整个字符串字符倒序，与旋转不是同一种操作。

相似题目

题目 难度 关联与区别
28. 找出字符串中第一个匹配项的下标 简单 等长串的旋转判定可转为在原串拼接自身后的文本中查找目标串。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/78865117
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！