题目地址
难度：⭐
题目描述：
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例1：
1
2
3
4
5
| 输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
|
示例2：
示例3：
1
2
3
4
5
| 输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
|
解题过程：
思路：没有想出比较高效的解法，期待官方题解指点迷津了。先找出所有可能满足题意的子串长度，然后用双指针去校验这个子串是否满足题意，注意这个子串长度从大到小进行可以提高效率（36ms->16ms）。
c++代码：(执行用时16ms，击败87.89%，内存消耗22.1M，击败10.80%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
bool repeatedSubstringPattern(string s) {
bool result=true;
int n=s.length();
for(int i=n/2;i>0;i--){
if(n%i==0){
if(this->repeatedSubstring(s,i)){
return true;
}
}
}
return false;
}
bool repeatedSubstring(string s,int len){
int n=s.length();
for(int p=len;p<n;p+=len){
for(int q=0;q<len;q++){
if(s[q]!=s[p+q]){
return false;
}
}
}
return true;
}
};
|
总结：
我使用的是方法一，但是还可以优化，找时间再学KMP算法。
