0459.重复的子字符串
难度：🟢 简单
标签：字符串、字符串匹配
链接：459. 重复的子字符串
题目描述
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba"
输出: false
示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
解题思路
核心思想
本题的核心思想是，如果一个字符串 s 可以由其子串重复构成，那么这个子串必然是 s 的一个前缀，并且 s 的长度必须是该子串长度的整数倍。
思路选择
枚举法 是解决此问题最直观的思路。我们可以遍历所有可能构成重复单元的子串长度。
可能的子串长度
i从 1 到s.length / 2。对于每个长度
i，我们首先检查s的总长度是否能被i整除。如果不能，则该长度的子串不可能构成s。如果可以整除，我们就取出长度为
i的前缀作为候选子串，然后检查用这个子串重复s.length / i次后，得到的新字符串是否与原字符串s相等。
关键步骤
循环遍历：从
i = 1循环到s.length / 2，i代表候选子串的长度。检查整除：判断
s.length是否能被i整除。如果不能，继续下一次循环。构建与比较：如果可以整除，取出前缀
sub = s.substring(0, i)，然后使用sub.repeat(s.length / i)构建重复字符串，并与原字符串s比较。返回结果：如果比较相等，说明找到了一个重复的子串模式，直接返回
true。如果循环结束后仍未找到，则返回false。
代码实现 (推荐)
/**
* @param {string} s
* @return {boolean}
*/
var repeatedSubstringPattern = function(s) {
const n = s.length;
// i 是子串的长度
for (let i = 1; i * 2 <= n; ++i) {
// 如果长度能被整除
if (n % i === 0) {
const sub = s.substring(0, i);
// 将子串重复相应次数，看是否与原串相等
if (sub.repeat(n / i) === s) {
return true;
}
}
}
return false;
};
原始代码分析 (用户提供)
您提供的代码采用了正确的枚举法思路，逻辑清晰，但可以通过使用内置方法使代码更简洁。
/**
* @param {string} s
* @return {boolean}
*/
var repeatedSubstringPattern = function (s) {
// i 是候选子串的长度
for (let i = 1; i <= s.length / 2; i++) {
const subStr = s.substr(0, i);
// 检查长度是否为约数
if (s.length % subStr.length === 0) {
const times = s.length / subStr.length;
let joinStr = subStr;
// 手动循环拼接字符串
for (let i = 1; i < times; i++) { // 注意：这里的 i 遮蔽了外层循环的 i
joinStr += subStr;
}
if (joinStr === s) return true;
}
}
return false;
};
优点：正确实现了核心算法逻辑。
待改进：
手动循环拼接字符串
joinStr += subStr不如使用内置的String.prototype.repeat()方法简洁和高效。内外层循环都使用了
i作为变量名，虽然在let作用域下不会出错，但容易引起混淆，建议使用不同的变量名。
复杂度分析
时间复杂度：O(n√n) 虽然外层循环看起来是 O(n)，但内层的字符串构建和比较也是 O(n)。不过，只有当子串长度
i是n的约数时才会执行内层操作。一个数n的约数个数远小于n，大约是n的1/3次方或更小，因此总时间复杂度远优于 O(n²)，更接近 O(n√n)。空间复杂度：O(n) 在比较时，需要构建一个与原字符串等长的新字符串，因此空间消耗是 O(n)。
相关题目
总结
本题是字符串处理的入门题，主要考察对问题进行分解和枚举的能力。枚举子串长度的思路非常直观。此外，本题还有一个非常巧妙的数学解法：将字符串 s 与自身拼接得到 s+s，移除首尾字符后，如果新的字符串中仍然包含原始的 s，则说明 s 是由重复子串构成的。例如 (s+s).substring(1, s.length * 2 - 1).includes(s)。