重复的子字符串
题目
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-substring-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
做了这么多题还是没什么好的想法,能想出来的就是暴力法,依次从头找子串比较后续的是否符合,直到字符串的中部.
领扣上有两位大神的想法:
- 将字符串与字符串拼接,掐头去尾后如果还包含原字符串即说明是由子串构成
假设字符串有n个子串构成,则拼接后的子串为2n个,掐头去尾后为2n-2个,如果此时的字符串至少包含一个原字符串,则说明至少包含n个子串,则2n-2>=n,n>=2.则说明该字符串是周期性结构,最少由两个子串构成.如果一个都不包含,即不包含n个子串,则说明2n-2<n,n<2,即n为1,也就是不符合周期性结构.
- 周期串为s,那么设定t表示周期,t在[1,s.length()-1]范围,依次针对每个t遍历看是否符合
代码
第一种解法
class Solution {
public boolean repeatedSubstringPattern(String s) {
String replace = s + s;
return replace.substring(1,replace.length()-1).contains(s);
}
}
第二种解法
class Solution {
public boolean repeatedSubstringPattern(String s) {
for(int t = 1;t <= s.length()/2;t++){
if(s.length()%t != 0){
continue;
}
for(int i = t;i < s.length() && s.charAt(i%t) == s.charAt(i);i++){
if(i == s.length()-1){
return true;
}
}
}
return false;
}
}
