LeetCode 796. 旋转字符串

约 4 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 5-10 字节跳动 美团 快手 华为
标签
字符串 字符串匹配
目录

题目描述

✅ 796. 旋转字符串

image-20230312172416619

题意分析

输入是两个小写字母串 s 和 goal，允许对 s 反复执行一种操作：把最左边的字符搬到最右边。要判断能否经过若干次这种操作把 s 变成 goal，返回布尔值。

这个操作不增删字符，只改变起点，所以每一步之后长度都不变、字符的多重集合也不变。做 n 次操作会回到原串，因此本质上只有 n 种不同结果，分别对应「从下标 0 到 n-1 各选一个位置作为新起点，然后环形读一圈」。

约束里字符串长度不超过 100，规模很小，$O(n^2)$ 完全可以接受，这意味着朴素枚举本身就是一种合格答案，追求线性只是加分项。

边界上要注意：允许操作 0 次，所以 s 与 goal 完全相同时应返回 true；两串长度不同时无论怎么转都不可能相等；两串都为空时返回 true。

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

核心思路

旋转不会改变字符的环形顺序，只是在选择新的起点。把长度为 n 的 s 左旋 k 次，结果为 s[k..n-1] + s[0..k-1]。把 s 复制一遍得到 s + s 后，这个「后缀 + 前缀」正好变成从下标 k 开始、长度为 n 的连续子串。

因此有如下充要条件：goal 是 s 的旋转串，当且仅当两串长度相等，并且 goal 是 s + s 的子串。

  • 必要性：若 goal 是左旋 k 次的结果，它就是 s + s 从 k 开始的长度 n 子串。
  • 充分性：长度相等时，s + s 中任何长度 n 的子串都恰好沿着 s 的环读一圈；起点为 n 时只是起点 0 的重复，也对应旋转 0 次。

本题 n <= 100，直接调用标准库做子串查找最短且足够可靠。若面试官禁止使用匹配 API，或要求明确的最坏 $O(n)$ 时间，再用 KMP 在 s + s 中匹配 goal；KMP 只替换「如何查子串」，不改变上述建模。

解题步骤

  1. 比较 s 与 goal 的长度；长度不同直接返回 false。
  2. 构造双倍字符串 s + s，把所有可能的环形起点展平成连续位置。
  3. 判断 goal 是否为双倍字符串的子串，命中返回 true，否则返回 false。

例如 s = "abcde"、goal = "cdeab"：s + s = "abcdeabcde"，其中从下标 2 开始的长度 5 子串就是 "cdeab"，所以左旋两次可达。若 goal = "abced"，即使字符组成相同，它也不是双倍字符串中的长度 5 子串，答案仍为 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)$。改用 KMP 后可保证整体为 $O(n)$。
  • 空间复杂度：$O(n)$，用于保存 s + s；KMP 版本还需要长度为 n 的前缀函数数组，渐进复杂度不变。

关键点总结

  • 「环形片段」常可通过复制一遍原序列展平成「连续片段」，从而消除取模下标。
  • len(s) == len(goal) 与子串判断缺一不可；前者保证匹配片段正好覆盖一整圈。
  • 证明建模时要同时说明必要性和充分性，不能只说“所有旋转都在 s + s 中”。
  • 标准库写法适合本题约束；KMP 是禁用 API 或要求最坏线性时间时的替代，不必默认增加实现复杂度。

易错点总结

  • 忘记先比较长度：s = "abcde"、goal = "abc" 时，goal 虽是 s + s 的子串，却不可能由旋转得到。
  • 只比较字符计数："abcde" 与 "abced" 的字符完全相同，但后者没有保持环形顺序。
  • 枚举旋转时漏掉 k = 0：原串与目标相同本来就应返回 true。
  • 手写匹配时把复杂度直接写成 $O(n)$：朴素匹配的最坏时间是 $O(n^2)$，只有使用 KMP 等线性匹配算法后才能保证 $O(n)$。

相似题目

题目 难度 考察点
面试题 01.09. 字符串轮转 简单 同一转化的换皮题，明确限制只能调用一次子串判断
28. 找出字符串中第一个匹配项的下标 简单 要返回匹配下标，是手写 KMP 的标准练习题
459. 重复的子字符串 简单 同样用拼接技巧，但要去掉首尾字符再查找自身
1408. 数组中的字符串匹配 简单 多串两两包含关系，考察枚举与去重
1668. 最大重复子字符串 简单 求最大重复次数，需要不断拼接模式串再匹配
214. 最短回文串 困难 拼接原串与反串后求前缀函数，是本题技巧的进阶用法