459. 重复的子字符串
459. 重复的子字符串
题目
Given a string s
, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Example 1:
Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.
Example 2:
Input: s = "aba"
Output: false
Example 3:
Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.
Constraints:
1 <= s.length <= 10^4
s
consists of lowercase English letters.
题目大意
给定一个非空的字符串 s
,检查是否可以通过由它的一个子串重复多次构成。
解题思路
循环遍历可能的子字符串长度:
- 通过一个循环遍历可能的子字符串长度,从长度为 1 到
n/2
遍历,n
是字符串的长度。我们只需要考虑到n/2
,因为一个子字符串重复构成的长度不能超过一半。
- 通过一个循环遍历可能的子字符串长度,从长度为 1 到
判断整除:
- 对于每一个可能的长度
i
,检查n % i == 0
。如果字符串长度能被i
整除,说明可以尝试用长度为i
的子字符串构建原字符串。
- 对于每一个可能的长度
判断整除:
- 通过
s.slice(0, i)
获取长度为i
的子字符串str
。 - 然后用
str.repeat(n / i)
来构建一个新的字符串,并与原字符串s
进行比较。如果相等,说明可以由该子字符串重复构成,返回true
。
- 通过
返回结果:
- 如果遍历完所有可能的长度仍然没有找到符合条件的子字符串,返回
false
。
- 如果遍历完所有可能的长度仍然没有找到符合条件的子字符串,返回
复杂度分析
- 时间复杂度:
O(n^2)
,外层循环的迭代次数最多为n/2
,而str.repeat(n / i)
操作的时间复杂度为O(n)
。因此,总的时间复杂度为O(n^2)
。 - 空间复杂度:
O(1)
,使用的额外空间主要是存储str
。
代码
/**
* @param {string} s
* @return {boolean}
*/
var repeatedSubstringPattern = function (s) {
const n = s.length;
for (let i = 1; i <= n / 2; i++) {
if (n % i == 0) {
const str = s.slice(0, i);
if (str.repeat(n / i) == s) {
return true;
}
}
}
return false;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
28 | 找出字符串中第一个匹配项的下标 | [✓] | 双指针 字符串 字符串匹配 | |
686 | 重复叠加字符串匹配 | 字符串 字符串匹配 |