LeetCode-重复的子字符串(459)

发布时间:2024年01月07日

题目描述:

给定一个非空的字符串 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);
        
    }
    
}
文章来源:https://blog.csdn.net/qq_45965652/article/details/135440866
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。