跳至主要內容

459. 重复的子字符串


459. 重复的子字符串open in new window

🟢   🔖  字符串 字符串匹配  🔗 力扣open in new window LeetCodeopen in new window

题目

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找出字符串中第一个匹配项的下标open in new window[✓]双指针 字符串 字符串匹配
686重复叠加字符串匹配open in new window字符串 字符串匹配