LeetCode——重复的子字符串

秒速五厘米 2022-03-17 12:34 264阅读 0赞

**题目**：

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

**示例 1:**

输入: "abab"
    
    输出: True
    
    解释: 可由子字符串 "ab" 重复两次构成。

**示例 2:**

输入: "aba"
    
    输出: False

**示例 3:**

输入: "abcabcabcabc"
    
    输出: True
    
    解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

**思路**：

简单的方案就是用窗口扫描，窗口大小先是1，然后每次不符合后，就增大。但是有些细节要注意，窗口大小必须被字符串大小整除，并且不能超过字符串大小的一半。

**代码**：

public boolean repeatedSubstringPattern(String s) {
            if(s.length() == 1){
                return false;
            }
            char[] str = s.toCharArray();
            //表示窗口
            int begin =0;
            int end =0;
            //窗口长度
            int Wlen = 1;
            //用于遍历字符串数组的索引
            int index = Wlen;
            boolean flag = true;
            //当遍历到最后一个字符串，则跳出
            while(index < str.length){
                for(int i = index,k = 0;k< Wlen;i++, k++){
                    flag = true;
                    //如果不匹配，则扩大窗口，并重新开始
                    if(str[k] != str[i]){
                        Wlen++;
                        //扩大窗口
                        while(str.length % Wlen !=0){
                            Wlen ++;
                            //如果找不到一个可以整除的WLen，则返回错误
                            if(Wlen * 2 > str.length){
                                return false;
                            }
                        }
                        //反正扩大后，直接跳出循环
                        flag = false;
                        index = Wlen;
                        break;
                    }
                }
                if(flag){
                    index += Wlen;
                }
            }
            return flag;
        }