LeetCode 459. 重复的子字符串

约 4 分钟
文章信息 12 个分类 5 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 字节跳动 微软 美团 阿里巴巴 快手 腾讯
标签
字符串 字符串匹配 扩展 KMP 字符串经典题 KMP 算法
目录

题目描述

✅ 459. 重复的子字符串

image-20230311200912538

题意分析

要判断的是：能不能找到一个非空子串，把它连续重复若干次（至少两次）后正好拼成原字符串。返回值只有真假两种，不需要给出那个子串本身。
有三个隐含条件必须先读出来：这个子串必须是原串的前缀，它的长度必须整除原串长度 n，并且长度不能等于 n——否则「重复一次」对任何字符串都成立，题目就没有意义了。
约束信号是长度上限一万且只含小写字母。一万这个量级意味着 $O(n^2)$ 级别的枚举也能通过，但出题人显然是想看有没有更漂亮的判定方式，所以这题在面试里几乎总会被追问「还有别的做法吗」。
边界：长度为 1 的字符串一定返回假，因为唯一的非空真前缀不存在；"aa" 这种最短的合法情形要返回真；全部字符相同的串永远返回真；而像 "aba" 这种长度为素数、首尾对称的串很容易骗过粗糙的判断，是必查的反例。

解法：拼接字符串去首尾判断

核心思路

若 s 由某个更短子串重复得到，那么把 s 向左旋转一个循环节的长度，结果仍是 s。而 s + s 的所有长度为 n 的子串，恰好对应 s 的各种旋转。

s 在 s + s 的下标 0 和 n 处一定出现，它们只是“旋转 0 位”的平凡匹配，不能作为答案。因此删掉拼接串的首尾字符，只保留下标 1..n-1 对应的非零旋转，再判断其中是否包含 s：

s 是重复子串构成 <=> (s + s)[1, 2n - 1) 包含 s

正向来看，若 s = t^k 且 k >= 2，从下标 |t| 开始仍能读出完整的 s，这个位置位于保留区间。反向来看，若 s 在某个 1 <= i < n 的位置匹配，说明旋转 i 位后字符串不变，因此字符按周期循环，s 可由长度 gcd(i, n) 的前缀重复得到；该长度严格小于 n。两个方向都成立，所以判定充分且必要。

解题步骤

  1. 拼接得到 doubled = s + s。
  2. 去掉 doubled 的第一个和最后一个字符，排除下标 0、n 的平凡匹配。
  3. 在剩余字符串中查找 s：找到说明存在非零旋转周期，返回 true；否则返回 false。

例如 s = "abab"，doubled = "abababab"，去掉首尾得到 "bababa"，其中包含 "abab"，所以返回 true。对于 "aba"，中间串是 "baab"，不包含原串，返回 false。单字符 "a" 的中间串为空，也会正确返回 false。

代码实现

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String doubled = s + s;
        return doubled.substring(1, doubled.length() - 1).contains(s);
    }
}

import "strings"

func repeatedSubstringPattern(s string) bool {
    doubled := s + s
    return strings.Contains(doubled[1:len(doubled)-1], s)
}

复杂度分析

  • 时间复杂度：构造中间串需要 O(n)；子串查找取决于标准库实现，使用线性匹配算法时为 O(n)，朴素匹配的最坏情况为 O(n^2)。若面试要求严格线性上界，可用 KMP 完成同一次查找。
  • 空间复杂度：O(n)，用于保存拼接字符串及中间串。

关键点总结

  • “由子串重复构成”等价于“经过某次非零旋转后仍等于自身”。
  • s + s 展开了所有旋转；删除首尾是为了同时排除两次原位匹配。
  • 不需要额外枚举循环节长度，非零旋转匹配已经隐含了周期与整除关系。
  • 面试中应能证明充要性，并主动说明库函数查找的复杂度依赖实现；若被限制不能调用库函数，再换 KMP。

易错点总结

  • 直接在 s + s 中查找 s，任何字符串都会在下标 0 匹配，结果恒为真。
  • 只删除首字符：下标 n 处仍保留一份完整原串，例如 "ab" 会被误判为真；首尾必须各删一个字符。
  • 枚举候选循环节时，必须同时满足长度小于 n 且能整除 n，否则字符串自身或不完整重复会被误判。
  • 单字符没有非空真子串，必须返回 false；首尾裁剪后的空串会自然处理该边界。
  • 复杂度不能无条件写成 O(n)，因为 contains / Contains 的最坏上界取决于具体标准库匹配实现。

相似题目

题目 难度 考察点
28. 找出字符串中第一个匹配项的下标 简单 要返回匹配下标而非真假，是手写 KMP 与 next 数组的正题
796. 旋转字符串 简单 同样用 s + s，但不砍首尾，还需先比较两串长度是否相等
面试题 01.09. 字符串轮转 简单 与 796 同解法换皮，限定只能调用一次判断子串的方法