LeetCode_46_RepeatedSubstringPattern

1. question: 重复的子字符串（简单）

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-substring-pattern

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

1 <= s.length <= 104
s 由小写英文字母组成

2. answers

这道题首先要明确的是：

1. 子串不是字符串本身。
2. 子串的首字符一定是字符串的首字符。
3. 子串的尾字符一定是字符串的尾字符。
4. 并且，以首字符开始的子串没有找到满足要求的子串；那么后续就没必要更换后续的首字符了（因为如果后续的满足了，那么必然该字符前面的子串满足条件，但是前面没找到，所以后续的一定不会满足。）。即子串一定是字符串的前缀。

找子串的时间复杂度为O(n)，判断子串是否满足要求的时间复杂度为O(n)，所以综合来看，时间复杂度为O(n^2)。

代码如下所示：

public class Solution_0043 {

    public static boolean repeatedSubstringPattern(String s) {

        char[] chars = s.toCharArray();

        int tempIndex = 0;
        boolean tag;

        // 找子串的结束位置，因为整个字符串不能作为子串，所以循环条件最多子串的1/2.
        // 注意，子串可以是单个字符
        for (int i = 0; i < chars.length / 2; i++) {

            // 找到子串
            if(chars[i] == chars[chars.length - 1]) {
                tag = true;
                tempIndex = 0;  // 注意，更新即将要比较的首位置

                // 判断子串是否满足要求。如果长度上不满足要求，则直接找下一个子串
                if(chars.length % (i + 1) != 0)
                    continue;

                // 长度满足要求后，比较内容，遍历完剩余的字符串，逐个比较子串(因为循环条件的原因，所以此时剩余字符串一定是大于等于子串的)
                // 而且上面的if判断保证了剩余字符串的长度是子串的倍数。所以，下面的比较保证了一定能一一比较完。
                for (int j = i + 1; j < chars.length; j++) {

                    // 重新赋值为子串首元素
                    if(tempIndex > i) tempIndex = 0;

                    if(chars[j] != chars[tempIndex++]) {
                        tag = false;
                        break;
                    }
                }

                if(tag) return true;
            }

        }

        return false;
    }

    public static void main(String[] args) {

//        String s = "abab";
        String s = "abaababaab";

        System.out.println(repeatedSubstringPattern(s));
    }
}

似乎这道题可以采用KMP算法来做，先暂时不考虑了。

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。