字符串轮转判定:用字符串哈希在 O(n) 时间内检查 s2 是否为 s1 的旋转字符串(LogicStack-LeetCode 题解)
字符串轮转判定:用字符串哈希在 O(n) 时间内检查 s2 是否为 s1 的旋转字符串(LogicStack-LeetCode 题解)
本文基于 LogicStack-LeetCode 仓库中「刷穿 LeetCode」系列《面试题 01.09. 字符串轮转(简单)》一文展开,结合仓库内 字符串哈希.md 专题索引与 187. 重复的DNA序列、686. 重复叠加字符串匹配 等姊妹题解,从问题本质、哈希原理到代码实现与易错点,给出可直接套用并提交的完整方案。
一、题目速览:什么是字符串轮转
本题是 LeetCode 上的《面试题 01.09. 字符串轮转》(来自《程序员面试金典》),难度为简单,题解 Tag 为「字符串哈希」。
题目要求:给定两个字符串 s1 和 s2,编写代码检查 s2 是否为 s1 旋转而成。所谓"旋转",可以理解为把字符串分成左右两段后交换位置,例如 waterbottle 旋转后可以得到 erbottlewat(把 wat 从头部挪到尾部)。
官方示例:
示例 1
输入:s1 = "waterbottle", s2 = "erbottlewat"
输出:True
示例 2
输入:s1 = "aa", s2 = "aba"
输出:False
约束提示:
- 字符串长度在 范围内,即两串长度均可为 0(空串);
- 题目追问了一句:"你能只调用一次检查子串的方法吗?"——这暗示了本题存在一条非常经典的捷径:利用
s1 + s1构造循环串,然后一次性判断s2是否为其子串(仓库中 796. 旋转字符串 正是这一思路的直白实现)。
二、核心思路:旋转关系等价于"循环子串"关系
本题的关键观察是等价转化:
若两字符串互为旋转,则「其一字符串」必然为「另一字符串拓展两倍长度后(循环子串)」的子串。
也就是说,s2 是 s1 的旋转 ⟺ s2 是 s1 + s1 中长度为 的连续子串。
这个等价关系可以这样理解:把 s1 复制一份拼在自己后面,得到长度为 的"环形展开"。此时以任意位置为起点、取连续 个字符,恰好穷举了 s1 的所有可能旋转结果(旋转 位,就是从 号位置开始取 个字符)。因此判断"是否互为旋转"就退化成了判断"长度为 的某个连续子段是否等于 s2",即一次标准的定长子串匹配。
仓库中 796. 旋转字符串(简单).md 用最直白的 contains 一句话解决了同构问题:
class Solution {
public boolean rotateString(String s, String goal) {
return s.length() == goal.length() && (s + s).contains(goal);
}
}
为什么 796 可以直接用 contains,而本题要上字符串哈希?区别在于本题的字符串长度可达 ,contains 底层 indexOf 的最坏复杂度并不稳定(详见 796 题解中对 HotSpot VM 内置 indexOf 指令优化的讨论:实测开启 _indexOf 内置优化后耗时约为原始实现的一半)。为了得到一个可严格证明为 的解法,本题采用「字符串哈希 + 前缀和」,把每次子串比较的代价降为 。
三、字符串哈希原理:O(1) 时间比较任意子串
字符串哈希(滚动哈希)的核心思想是:把字符串看成一个 进制数,通过预处理得到哈希前缀数组 h[] 与 次方数组 p[],之后任意子串 s[i..j] 的哈希值都可以用前缀和公式在 时间内算出。
3.1 两个核心数组的构造
h[i]:前 个字符(下标从 1 开始)构成的哈希值,递推式:h[i] = h[i - 1] * P + s.charAt(i - 1)p[i]:进制 的 次幂,递推式:p[0] = 1; p[i] = p[i - 1] * P
3.2 子串哈希公式
要计算下标从 1 开始的子串 s[i..j] 的哈希值,使用前缀和思想:
cur = h[j] - h[i - 1] * p[j - i + 1]
h[j] 包含的是前 个字符的信息,h[i - 1] 是前 个字符的信息;把 h[i - 1] 乘以 (即 p[j - i + 1])对齐位数后相减,正好"抠出"中间这一段长度为 的子串哈希。整个过程只涉及常数次乘减运算,与子串长度无关,因此单次子串比较是 的。
3.3 取模的关键细节
原文档特别强调了一个跨语言差异:
一些细节:其他语言可能不像
Java那样存在自然取模,可手动取模,对于自带高精度的语言若不取模会导致单次计算复杂度上升,会TLE。
- Java:
int乘法溢出后自动截断(等价于对 取模),h[j] - h[i - 1] * p[j - i + 1]直接写即可,无需显式取模; - Python:整数是任意精度的,若不取模,哈希值会指数级膨胀成大整数,单次乘法的复杂度不再视为 ,整体会超时。因此 Python 代码里必须显式
% MOD,仓库文档选用的模数为987654321。
仓库中 187. 重复的DNA序列(中等).md 还针对"哈希冲突"给出了更细致的经验:
- 溢出确实可能让哈希值变负数,当且仅当两个哈希值溢出程度与
Integer.MAX_VALUE呈不同倍数关系时会产生错误结果(即哈希冲突),此时应换更大的进制 ,或用long扩大表示范围; - 的选取经验:通常从 开始尝试,被卡样例后换 ,再不行就换更大的质数。本题采用的 即属于这一套路。
四、完整题解:Java 与 Python 双版本
先计算 s2 的完整哈希值 t,再构造 s1 + s1 的 h[] 与 p[] 数组,枚举所有长度为 的连续子段,检查是否存在哈希值等于 t 的子段。
4.1 Java 版本(利用 int 自然溢出取模)
class Solution {
static int N = 200010, P = 13131;
static int[] h = new int[N], p = new int[N];
public boolean isFlipedString(String s1, String s2) {
if (s1.length() != s2.length()) return false;
int n = s1.length();
// 预处理 s2 的哈希值 t
for (int i = 1; i <= n; i++) h[i] = h[i - 1] * P + s2.charAt(i - 1);
int t = h[n]; // s2 hash
// 构造 s1 + s1 的哈希数组与次方数组
s1 = s1 + s1;
p[0] = 1;
for (int i = 1; i <= 2 * n; i++) {
h[i] = h[i - 1] * P + s1.charAt(i - 1);
p[i] = p[i - 1] * P;
}
// 枚举长度为 n 的连续子段,O(1) 比较哈希值
for (int i = 1; i + n - 1 <= 2 * n; i++) {
int j = i + n - 1, cur = h[j] - h[i - 1] * p[j - i + 1];
if (cur == t) return true;
}
return false;
}
}
4.2 Python 版本(必须手动取模)
N, P, MOD = 200010, 13131, 987654321
h, p = [0] * N, [1] * N
class Solution:
def isFlipedString(self, s1: str, s2: str) -> bool:
if len(s1) != len(s2):
return False
if s1 == s2:
return True
n = len(s1)
# 预处理 s2 的哈希值 t
for i in range(1, n + 1):
h[i] = (h[i - 1] * P + ord(s2[i - 1])) % MOD
t = h[n]
# 构造 s1 + s1 的哈希数组与次方数组
s1 = s1 + s1
for i in range(1, 2 * n + 1):
h[i] = (h[i - 1] * P + ord(s1[i - 1])) % MOD
p[i] = (p[i - 1] * P) % MOD
# 枚举长度为 n 的连续子段,比较哈希值
for i in range(1, n + 1):
j = i + n - 1
cur = (h[j] - h[i - 1] * p[j - i + 1]) % MOD
if cur == t:
return True
return False
注意 Python 版额外加了 if s1 == s2: return True 的短路判断(两串相等时 0 次旋转即满足条件),属于防御性写法,Java 版即便不加也能被后续循环自然覆盖。
4.3 复杂度分析
- 时间复杂度:。预处理
s2的哈希、构造s1 + s1的h[]/p[]各需 ,枚举 个子段每次比较 ; - 空间复杂度:。
h[]与p[]数组长度约为 。
对比 796 题中 (s + s).contains(s2) 的做法,字符串哈希版本给出了可证明的最坏线性复杂度,在 逼近 时更稳健。
五、边界情况与易错点清单
- 长度不等直接返回 false:旋转不会改变字符串长度,这是最强的剪枝条件,必须放在第一步;
- 空串特判:两串长度均为 0 时,
n = 0,循环不执行,需要保证代码在该场景下不越界(两版本均天然满足); - Java 静态数组的复用:
h[]、p[]声明为static且数组大小固定为N = 200010,原因是s1 + s1最长可达 ,必须预留足够空间;static修饰可减少重复 new 的开销; - 下标从 1 开始:哈希前缀数组统一采用"1-based"下标(
h[0] = 0),公式cur = h[j] - h[i - 1] * p[j - i + 1]才成立,混用 0-based 是常见笔误; - 进制与模数的选择:(质数)与 是仓库经过实践验证的取值;若出现哈希冲突导致 WA,按 187 题解的经验依次尝试更大的质数或改用
long; - Python 不取模必 TLE:因为 Python 大整数任意精度,忘写
% MOD会让哈希值指数级膨胀,把 的乘法退化成长整数运算。
六、同主题延伸:仓库中的"旋转/重复匹配"题族
本题在 LogicStack-LeetCode 仓库中与多道题目构成完整的知识链路,非常适合对照阅读:
| 题目 | 难度 | 核心技法 | 仓库路径 |
|---|---|---|---|
| 面试题 01.09. 字符串轮转 | 简单 | 字符串哈希(本文) | LeetCode/面试题/面试题 01.09. 字符串轮转(简单).md |
| 796. 旋转字符串 | 简单 | 模拟 + (s + s).contains(goal) |
LeetCode/791-800/796. 旋转字符串(简单).md |
| 686. 重复叠加字符串匹配 | 中等 | 字符串哈希 / KMP / 上下界分析 | LeetCode/681-690/686. 重复叠加字符串匹配(中等).md |
| 187. 重复的DNA序列 | 中等 | 字符串哈希 + 前缀和 | LeetCode/181-190/187. 重复的DNA序列(中等).md |
其中值得展开的两点:
- 686. 重复叠加字符串匹配:问题变成"把
a重复叠加多少次后b成为其子串"。其题解给出的上下界结论(下界为 ,上界为下界 + 1)与本题"复制两倍后枚举定长子串"的框架一脉相承,并且在同一份题解里给出了字符串哈希、KMP 与indexOf三种子串匹配手段的对比实现,是学习"定长子串匹配"的最佳进阶材料; - 187. 重复的DNA序列:同样使用
h[]、p[]与公式h[j] - h[i - 1] * p[j - i + 1],但把子串哈希值当作Integer直接作为HashMap的 key 来做计数——它提醒我们一个细节:若用String作为 key,hashCode()会遍历整个字符串,使计数过程重新与长度挂钩,破坏严格 。
此外,仓库根目录的 Index/字符串哈希.md 汇总了「字符串哈希」专题的全部题目索引(包括 187、472、686、1044、1668 等),学习时可按专题索引系统刷题。
七、小结
本题的价值不在于"难",而在于示范了一个高频套路:旋转类字符串问题 ⟹ 双倍展开 ⟹ 定长子串匹配。在此基础上:
- 若追求代码极简、且
indexOf在该语言/平台上足够快(如仓库 796 题解讨论的 HotSpot VM 优化场景),可直接(s + s).contains(s2); - 若追求可证明的 最坏复杂度,则用「字符串哈希 + 前缀和」,把每次子串比较压到 ,这也是仓库本题解给出的标准做法,Java 靠
int溢出自然取模、Python 需显式% MOD。
掌握"双倍串 + 定长子串哈希"这一组合后,面试题 01.09、796、686 乃至 187 这类问题都可以在几分钟内写出正确且高效的代码。