(字符串 ) 459. 重复的子字符串——【Leetcode每日一题】-Toy模板网

这篇具有很好参考价值的文章主要介绍了(字符串 ) 459. 重复的子字符串——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

❓459. 重复的子字符串

难度：简单

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

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。

示例 2:

输入: s = “aba”
输出: false

示例 3:

输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

提示：

$1 <= s.length <= 10^4$
s 由小写英文字母组成

💡思路：

法一：暴力

就是一个 for 循环获取子串的终止位置，然后判断子串是否能重复构成字符串，又嵌套一个 for循环，所以是 $O(n^2)$ 的时间复杂度。

法二： KMP(后续更新)

🍁代码：(Java、C++)

法一：暴力

Java

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for(int i = 1; i <= n / 2; i++){
            if(n % i != 0) continue;
            for(int j = 0; j <= n - 2 * i; j += i){
                String str1 = s.substring(j, j + i);
                String str2 = s.substring(j + i, j + 2 * i);
                if(str1.compareTo(str2) != 0) break;
                if(j == n - 2 * i) return true;
            }
        }
        return false;
    }
}

C++

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for(int i = 1; i <= n / 2; i++){
            if(n % i != 0) continue;
            for(int j = 0; j <= n - 2 * i; j += i){
                if(s.compare(j, i, s, j + i, i) != 0) break;
                if(j == n - 2 * i) return true;
            }
        }
        return false;
    }
};