LeetCode 459 - 重复的子字符串

摘要

这道题的描述非常短，看起来像是字符串基础题，但它其实是那种**“一眼暴力，二眼不稳，三眼才发现规律”**的典型。

很多人第一反应是暴力枚举子串，但真正优雅、好记、好解释的解法，其实和字符串的自我重复特性有关。一旦你理解了这个性质，这题会变得异常简单，而且还特别容易写出又短又稳的代码

描述

题目给你一个非空字符串s，问你一件事：

能不能用s的某一个子串，重复多次，刚好拼出整个s？

注意几个关键点：

• 子串不能是空串
• 必须重复两次或以上
• 拼出来的结果要和原字符串完全一致

举几个直观的例子：

• "abab"→"ab" + "ab"，成立
• "aba"→ 怎么拆都不行
• "abcabcabcabc"→"abc"重复 4 次，或者"abcabc"重复 2 次

这类问题在实际开发中其实并不少见，比如：

• 判断一个字符串是不是某种周期性模式
• 判断日志 key、配置 key 是否被错误复制
• 校验前端传过来的某些 pattern 字符串是否合法

题解答案

这道题我推荐你记住一个非常经典、非常好用的技巧：

如果字符串s是由某个子串重复构成的
那么s一定是(s + s)去掉首尾字符之后的子串

判断条件一句话就够：

(s + s).dropFirst().dropLast().contains(s)

如果包含，答案就是true，否则是false。

题解代码分析

为什么这个技巧是成立的？

我们一步步来解释，不搞“玄学结论”。

假设原字符串是：

s = "abab"

那它本身是"ab"重复得到的。

我们把它拼接一次：

s + s = "abababab"

然后把第一个字符和最后一个字符去掉：

"bababa"

你会发现，"abab"依然完整地出现在中间。

反过来看为什么不成立的情况会失败

比如：

s = "aba" s + s = "abaaba" 去头去尾 -> "baab"

你会发现"aba"根本不在里面。

原因在于：
如果一个字符串不是周期性构成的，它在“错位拼接”后是无法完整对齐自己的。

这个解法本质在干嘛？

从本质上看，它是在做一件事：

• 利用字符串的循环特性
• 用一次拼接，把所有“可能的周期错位”都包含进来
• 如果还能完整匹配原串，说明一定存在周期

这是一个非常典型的字符串性质判断，而不是暴力搜索。

Swift 可运行 Demo 代码

importFoundationclassSolution{funcrepeatedSubstringPattern(_s:String)->Bool{// 长度为 1 的字符串不可能由子串重复构成ifs.count<=1{returnfalse}letdoubled=s+s// 去掉首尾字符letstartIndex=doubled.index(after:doubled.startIndex)letendIndex=doubled.index(before:doubled.endIndex)lettrimmed=doubled[startIndex..<endIndex]returntrimmed.contains(s)}}

代码逐行解释一下

ifs.count<=1{returnfalse}

这个是边界处理，很重要。
单字符字符串，比如"a"，显然没法重复构成。

letdoubled=s+s

核心操作，把字符串拼接一次。

letstartIndex=doubled.index(after:doubled.startIndex)letendIndex=doubled.index(before:doubled.endIndex)

Swift 的字符串是Character 级别索引，不能直接用整数下标，这里一定要用index(after:)和index(before:)。

lettrimmed=doubled[startIndex..<endIndex]

去掉首尾字符，制造“错位空间”。

returntrimmed.contains(s)

判断原字符串是否还能在中间被完整匹配。

示例测试及结果

letsolution=Solution()print(solution.repeatedSubstringPattern("abab"))// trueprint(solution.repeatedSubstringPattern("aba"))// falseprint(solution.repeatedSubstringPattern("abcabcabcabc"))// trueprint(solution.repeatedSubstringPattern("a"))// false

输出结果：

true false true false

完全符合题目预期。

与实际场景结合

这个问题在工程里其实很常见，只是换了种“马甲”。

举几个真实点的例子：

1. 配置检测

   • "env.env.env"这种字符串，是否是误配置？

2. 日志 pattern 分析

   • 判断某段日志 key 是否被程序错误地重复拼接

3. 前端动画 / CSS pattern

   • 是否是周期性样式字符串

4. 数据清洗

   • 判断某字段是否为简单模板复制，而非真实数据

这道题的解法，本质就是在帮你判断：
一个字符串是否“只有表面变化，本质重复”。

时间复杂度

O(n)

字符串拼接 + 子串查找，整体是线性复杂度。

在s.length <= 10^4的限制下，完全没有压力。

空间复杂度

O(n)

主要来自s + s生成的新字符串。

总结

这道题非常适合作为：

• 字符串性质题的入门
• 面试时考察“有没有见过经典技巧”
• 提醒自己：别急着写暴力

你完全可以记住一句话作为总结：

判断字符串是否由重复子串构成，本质不是找子串，而是判断字符串是否“能在自身的错位拷贝中重新出现”。