字符串轮转判定:用字符串哈希在 O(n) 时间内检查 s2 是否为 s1 的旋转字符串(LogicStack-LeetCode 题解)

原创2026-10-10 23:45:001,918 阅读
文章标签:教程文档

字符串轮转判定:用字符串哈希在 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,100000][0, 100000] 范围内,即两串长度均可为 0(空串);
  • 题目追问了一句:"你能只调用一次检查子串的方法吗?"——这暗示了本题存在一条非常经典的捷径:利用 s1 + s1 构造循环串,然后一次性判断 s2 是否为其子串(仓库中 796. 旋转字符串 正是这一思路的直白实现)。

二、核心思路:旋转关系等价于"循环子串"关系

本题的关键观察是等价转化:

若两字符串互为旋转,则「其一字符串」必然为「另一字符串拓展两倍长度后(循环子串)」的子串。

也就是说,s2 是 s1 的旋转 ⟺ s2 是 s1 + s1 中长度为 n=∣s1∣n = |s1| 的连续子串。

这个等价关系可以这样理解:把 s1 复制一份拼在自己后面,得到长度为 2n2n 的"环形展开"。此时以任意位置为起点、取连续 nn 个字符,恰好穷举了 s1 的所有可能旋转结果(旋转 kk 位,就是从 kk 号位置开始取 nn 个字符)。因此判断"是否互为旋转"就退化成了判断"长度为 nn 的某个连续子段是否等于 s2",即一次标准的定长子串匹配。

仓库中 796. 旋转字符串(简单).md 用最直白的 contains 一句话解决了同构问题:

class Solution {
    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && (s + s).contains(goal);
    }
}

为什么 796 可以直接用 contains,而本题要上字符串哈希?区别在于本题的字符串长度可达 10510^5,contains 底层 indexOf 的最坏复杂度并不稳定(详见 796 题解中对 HotSpot VM 内置 indexOf 指令优化的讨论:实测开启 _indexOf 内置优化后耗时约为原始实现的一半)。为了得到一个可严格证明为 O(n)O(n) 的解法,本题采用「字符串哈希 + 前缀和」,把每次子串比较的代价降为 O(1)O(1)。

三、字符串哈希原理:O(1) 时间比较任意子串

字符串哈希(滚动哈希)的核心思想是:把字符串看成一个 PP 进制数,通过预处理得到哈希前缀数组 h[] 与 次方数组 p[],之后任意子串 s[i..j] 的哈希值都可以用前缀和公式在 O(1)O(1) 时间内算出。

3.1 两个核心数组的构造

  • h[i]:前 ii 个字符(下标从 1 开始)构成的哈希值,递推式: h[i] = h[i - 1] * P + s.charAt(i - 1)
  • p[i]:进制 PP 的 ii 次幂,递推式: 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] 包含的是前 jj 个字符的信息,h[i - 1] 是前 i−1i - 1 个字符的信息;把 h[i - 1] 乘以 Pj−i+1P^{j - i + 1}(即 p[j - i + 1])对齐位数后相减,正好"抠出"中间这一段长度为 j−i+1j - i + 1 的子串哈希。整个过程只涉及常数次乘减运算,与子串长度无关,因此单次子串比较是 O(1)O(1) 的。

3.3 取模的关键细节

原文档特别强调了一个跨语言差异:

一些细节:其他语言可能不像 Java 那样存在自然取模,可手动取模,对于自带高精度的语言若不取模会导致单次计算复杂度上升,会 TLE。

  • Java:int 乘法溢出后自动截断(等价于对 2322^{32} 取模),h[j] - h[i - 1] * p[j - i + 1] 直接写即可,无需显式取模;
  • Python:整数是任意精度的,若不取模,哈希值会指数级膨胀成大整数,单次乘法的复杂度不再视为 O(1)O(1),整体会超时。因此 Python 代码里必须显式 % MOD,仓库文档选用的模数为 987654321。

仓库中 187. 重复的DNA序列(中等).md 还针对"哈希冲突"给出了更细致的经验:

  • 溢出确实可能让哈希值变负数,当且仅当两个哈希值溢出程度与 Integer.MAX_VALUE 呈不同倍数关系时会产生错误结果(即哈希冲突),此时应换更大的进制 PP,或用 long 扩大表示范围;
  • PP 的选取经验:通常从 131131 开始尝试,被卡样例后换 1313113131,再不行就换更大的质数。本题采用的 P=13131P = 13131 即属于这一套路。

四、完整题解:Java 与 Python 双版本

先计算 s2 的完整哈希值 t,再构造 s1 + s1 的 h[] 与 p[] 数组,枚举所有长度为 nn 的连续子段,检查是否存在哈希值等于 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 复杂度分析

  • 时间复杂度:O(n)O(n)。预处理 s2 的哈希、构造 s1 + s1 的 h[]/p[] 各需 O(n)O(n),枚举 nn 个子段每次比较 O(1)O(1);
  • 空间复杂度:O(n)O(n)。h[] 与 p[] 数组长度约为 2n2n。

对比 796 题中 (s + s).contains(s2) 的做法,字符串哈希版本给出了可证明的最坏线性复杂度,在 nn 逼近 10510^5 时更稳健。

五、边界情况与易错点清单

  1. 长度不等直接返回 false:旋转不会改变字符串长度,这是最强的剪枝条件,必须放在第一步;
  2. 空串特判:两串长度均为 0 时,n = 0,循环不执行,需要保证代码在该场景下不越界(两版本均天然满足);
  3. Java 静态数组的复用:h[]、p[] 声明为 static 且数组大小固定为 N = 200010,原因是 s1 + s1 最长可达 2×1052 \times 10^5,必须预留足够空间;static 修饰可减少重复 new 的开销;
  4. 下标从 1 开始:哈希前缀数组统一采用"1-based"下标(h[0] = 0),公式 cur = h[j] - h[i - 1] * p[j - i + 1] 才成立,混用 0-based 是常见笔误;
  5. 进制与模数的选择:P=13131P = 13131(质数)与 MOD=987654321MOD = 987654321 是仓库经过实践验证的取值;若出现哈希冲突导致 WA,按 187 题解的经验依次尝试更大的质数或改用 long;
  6. Python 不取模必 TLE:因为 Python 大整数任意精度,忘写 % MOD 会让哈希值指数级膨胀,把 O(1)O(1) 的乘法退化成长整数运算。

六、同主题延伸:仓库中的"旋转/重复匹配"题族

本题在 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 成为其子串"。其题解给出的上下界结论(下界为 ⌈m/n⌉\lceil m/n \rceil,上界为下界 + 1)与本题"复制两倍后枚举定长子串"的框架一脉相承,并且在同一份题解里给出了字符串哈希、KMP 与 indexOf 三种子串匹配手段的对比实现,是学习"定长子串匹配"的最佳进阶材料;
  • 187. 重复的DNA序列:同样使用 h[]、p[] 与公式 h[j] - h[i - 1] * p[j - i + 1],但把子串哈希值当作 Integer 直接作为 HashMap 的 key 来做计数——它提醒我们一个细节:若用 String 作为 key,hashCode() 会遍历整个字符串,使计数过程重新与长度挂钩,破坏严格 O(n)O(n)。

此外,仓库根目录的 Index/字符串哈希.md 汇总了「字符串哈希」专题的全部题目索引(包括 187、472、686、1044、1668 等),学习时可按专题索引系统刷题。

七、小结

本题的价值不在于"难",而在于示范了一个高频套路:旋转类字符串问题 ⟹ 双倍展开 ⟹ 定长子串匹配。在此基础上:

  • 若追求代码极简、且 indexOf 在该语言/平台上足够快(如仓库 796 题解讨论的 HotSpot VM 优化场景),可直接 (s + s).contains(s2);
  • 若追求可证明的 O(n)O(n) 最坏复杂度,则用「字符串哈希 + 前缀和」,把每次子串比较压到 O(1)O(1),这也是仓库本题解给出的标准做法,Java 靠 int 溢出自然取模、Python 需显式 % MOD。

掌握"双倍串 + 定长子串哈希"这一组合后,面试题 01.09、796、686 乃至 187 这类问题都可以在几分钟内写出正确且高效的代码。

登录后查看全文
LogicStack-LeetCode