LeetCode-重复的子字符串（459）

题目描述：

给定一个非空的字符串 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);
        
    }
    
}