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

本文主要是介绍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);}}

这篇关于LeetCode-重复的子字符串（459）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---