Leetcode 459——重复的子字符串

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 1 <= s.length <= 10e4
• s 由小写英文字母组成

第一次看到这个题，我下意识的思路是利用哈希表去统计字符串中每个字符出现的次数，然后通过遍历，若是每两个字符次数的最小公因数都相等且不等于1，那么该字符串就可以由子串重复多次构成，显然这种方法思路时间复杂度很高，于是我通过逛评论区，看到了一种更加新奇的思路。

假设母串S是由子串s重复N次而成， 则 S+S则有子串s重复2N次， 那么现在有： S=Ns， S+S=2Ns， 其中N>=2。 如果条件成立， S+S=2Ns, 掐头去尾破坏2个s，S+S中还包含2*（N-1）s, 又因为N>=2, 因此S在掐头去尾后的2S中必然出现一次以上，掐头去尾可以通过通过截取第一个字符和最后一个字符去破坏头和尾的字符串。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String str = (s + s).substring(1,s.length()*2-1);
        if(str.contains(s))
        {
            return true;
        }
        return false;
    }
}

实现思路的代码编写能力固然重要，但是一个好的思路可以使得效率事半功倍。