【LeetCode】459. 重复的子字符串（简单）——代码随想录算法训练营Day09

题目链接：459. 重复的子字符串

题目描述

给定一个非空的字符串?s?，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"

输出: true

解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"

输出: false

示例 3:

输入: s = "abcabcabcabc"

输出: true

解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• 1 <= s.length <= 104
• s?由小写英文字母组成

文章讲解：代码随想录

视频讲解：字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串_哔哩哔哩_bilibili

题解1：暴力法（失败）

思路：直接暴力查找所有字串，对比是不是和主串匹配。

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    // i 为子串的长度
    for (let i = 1; i < s.length; i++) {
        let flag = true;
        for (let j = 0; j < s.length; j++) {
            if (s[j] !== s[j % i]) {
                flag = false;
                break;
            }
        }
        if (flag && s.length % i === 0) {
            return true;
        }
    }
    return false;
};

分析：时间复杂度为 O(n2)，空间复杂度为 O(1)。

不出意料，暴力法解题失败，超出时间限制，需要寻找时间复杂度更低的解法。

题解2：移动匹配

思路：假设一个字符串 s 由 n 个子串 t 构成，则 2s 由 2n 个 t构成，这样在 2s 中间一定会找到 s。

将字符串本身复制2倍得到一个新字符串，去除新字符串首尾的字符，若可以在新字符串中找到原字符串，则此字符串可以由多个相同的子串重复组成。

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    return (s + s).substring(1, s.length * 2 - 1).indexOf(s) >= 0;
};

分析：时间复杂度为 O(n)，空间复杂度为 O(n)。

题解3：KMP

思路：一个字符串如果能由多个相同的子串重复组成，那么它的长度减去其最长相等前后缀的部分可以被它的长度整除。

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    let j = 0;
    const next = [0];
    for (let i = 1; i < s.length; i++) {
        while (j > 0 && s[i] !== s[j]) {
            j = next[j - 1];
        }
        if (s[i] === s[j]) {
            j++;
        }
        next[i] = j;
    }
    return next[s.length - 1] > 0 && s.length % (s.length - next[s.length - 1]) === 0;
};

分析：时间复杂度为 O(n)，空间复杂度为 O(n)。

收获

了解了 KMP 算法在字符串模式匹配中的应用，进一步提升自己的编码能力。