给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。
思路一: 使用枚举的方法。首先因为字符串s有一个子串重复多次构成,那么s的长度len与子串的长度subLen应该成倍数关系,并且在s中索引为i的字符应该与索引为i+subLen的字符相等。根据这些我们可以首先设置一个循环对从1到len/2的子串长度进行处理(因为子串至少重复一次所以最大长度为len/2),接着判断子串长度是否和s长度len成倍数关系,如果是就再设置一个for循环来对s中的每一个字符进行验证,如果在字符串s中索引为j的字符不等于索引为j-i的字符(在下面代码中,i为子串长度)则设置要返回的布尔型设置为false。每次内层for循环结束后都要判断设置布尔型变量是否为true,如果为true直接返回,为false则按照外层循环递增的子串长度继续执行代码,如果整个双层循环执行完都未返回则说明字符串s不符合条件,直接返回false。
思路二: 第二种思路比较简单,因为符合条件的字符串s都是由多个子串n重复组成的,所以这里将s表示为kn+n,相当于s1=kn,s2=n,s=s1+s2。所以将两个s拼接成一个新的字符串,并且删除首尾两个字符,那么新字符串从s1+s2+s1+s2变成了s3+s2+s1+s4,这时只需判断这个字符串内是否包含原字符串s即可。
代码:
class Solution {
public boolean repeatedSubstringPattern(String s) {
//return repeatedSubstringPattern1(s);
return repeatedSubstringPattern2(s);
}
public boolean repeatedSubstringPattern1(String s) {
if(s.length()==1) {
return false;
}
int len=s.length();
for(int i=1;i<=len/2;i++) {
if(len%i==0) {
boolean match=true;
for(int j=i;j<len;j++) {
if(s.charAt(j)!=s.charAt(j-i)) {
match=false;
break;
}
}
if(match) {
return true;
}
}
}
return false;
}
public boolean repeatedSubstringPattern2(String s) {
String str=s+s;
return str.substring(1,str.length()-1).contains(s);
}
}