問題：

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Example 1:

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"
Output: False

Example 3:

Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

大意：

給出一個(gè)非空字符串，檢查它是否可以由它的子字符串重復(fù)組成。你可以假設(shè)給出的字符串全部由小寫字母組成并且它的長度不超過10000。
例1：

輸入：“abab”
輸出：True
解釋：重復(fù)兩次子字符串 “ab”。

例2：

輸入：“aba”
輸出：False

例3：

輸入：“abcabcabc”
輸出：True
解釋：多次重復(fù)子字符串 “abc”。（或者重復(fù)兩次子字符串 “abcabc”。）

思路：

這道題我的想法是，檢測是否由子字符串重復(fù)組成，只需要看是不是可以后面部分的字符串與前面的字符串完全一樣就可以了。

首先如果字符串的字母數(shù)小于兩個(gè)，那也不用判斷了，一定不可能是多個(gè)子字符串重復(fù)出來的。

設(shè)立兩個(gè)標(biāo)記，一個(gè)快一點(diǎn)一個(gè)慢一點(diǎn)。快的從第二個(gè)字母開始往后遍歷，找到與第一個(gè)字母一樣的，就停下來開始判斷，慢的從第一個(gè)字母開始，兩個(gè)標(biāo)記一起往后遍歷，看是不是可以完全一致，一直到最后一個(gè)字母，如果從后面開始的與從頭開始的一模一樣，說明是存在重復(fù)的字符串，并且由它重復(fù)組成的。

如果遍歷時(shí)又出現(xiàn)不一樣了，這時(shí)候說明還不是重復(fù)的，就要繼續(xù)當(dāng)做從頭開始找了，繼續(xù)往后遍歷快的標(biāo)記，找與第一個(gè)字母一樣的，然后重復(fù)上面的過程，注意找到后慢的標(biāo)記需要回到第一個(gè)字母。

不管找沒找到，當(dāng)快的遍歷到最后字母了就停止遍歷了，這時(shí)如果是沒找到的狀態(tài)，那就直接false了，如果是找到的狀態(tài)，那么有可能是確實(shí)重復(fù)組成的，也有可能只是最后一小節(jié)和前面的一樣，中間的一段還是沒有重復(fù)的，這時(shí)候根據(jù)慢的標(biāo)記來判斷，如果慢的標(biāo)記已經(jīng)走過了整個(gè)字符串的一半，就說明至少是二分之一的子字符串重復(fù)兩次得到的，或者更小的字符串重復(fù)多次。如果慢的標(biāo)記還沒走過一半，說明中間還有一部分并沒有來得及重復(fù)，這時(shí)候就依然是false了。在判斷慢的是否過半了時(shí)，由于存在整個(gè)字符串長度可能為基數(shù)也可能為偶數(shù)的情況，所以用慢標(biāo)記的位置乘以二來和整體長度作比較進(jìn)行判斷比較合適。

這個(gè)方法只需要遍歷一次字符串，時(shí)間復(fù)雜度只有O（n），還是很快的，實(shí)際結(jié)果也打敗了95%的人~

代碼（Java）：

public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        if (str.length() < 2) return false;
        
        char[] arr = str.toCharArray();
        int low = 0;
        int fast = 1;
        boolean match = false;// 匹配到與否的標(biāo)記
        while (fast < arr.length) {
            if (arr[fast] == arr[0]) {
                // 匹配到了第一個(gè)，開始判斷是否重復(fù)
                for (low = 0; fast < arr.length;) {
                    if (arr[low] == arr[fast]) {// 往后走進(jìn)行不斷判斷
                        match = true;
                        low++;
                        fast++;
                    } else {// 匹配不一致，跳出去重新找
                        match = false;
                        break;
                    }
                }
            } else {// 沒能匹配首字母
                match = false;
                fast++;
            }
        }
        return match && low*2 >= arr.length;
    }
}

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首頁