459. 重复的子字符串

🟢   🔖  字符串 字符串匹配  🔗 LeetCode

题目

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. 循环遍历可能的子字符串长度：

   • 通过一个循环遍历可能的子字符串长度，从长度为 1 到 n/2 遍历，n 是字符串的长度。我们只需要考虑到 n/2，因为一个子字符串重复构成的长度不能超过一半。

2. 判断整除：

   • 对于每一个可能的长度 i，检查 n % i == 0。如果字符串长度能被 i 整除，说明可以尝试用长度为 i 的子字符串构建原字符串。

3. 判断整除：

   • 通过 s.slice(0, i) 获取长度为 i 的子字符串 str。
   • 然后用 str.repeat(n / i) 来构建一个新的字符串，并与原字符串 s 进行比较。如果相等，说明可以由该子字符串重复构成，返回 true。

4. 返回结果：

   • 如果遍历完所有可能的长度仍然没有找到符合条件的子字符串，返回 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	重复叠加字符串匹配		字符串 字符串匹配