內(nèi)容

給定一個(gè)非空的字符串，判斷它是否可以由它的一個(gè)子串重復(fù)多次構(gòu)成。給定的字符串只含有小寫(xiě)英文字母，并且長(zhǎng)度不超過(guò)10000。

示例 1:

輸入: "abab"

輸出: True

解釋: 可由子字符串 "ab" 重復(fù)兩次構(gòu)成。
示例 2:

輸入: "aba"

輸出: False
示例 3:

輸入: "abcabcabcabc"

輸出: True

解釋: 可由子字符串 "abc" 重復(fù)四次構(gòu)成。 (或者子字符串 "abcabc" 重復(fù)兩次構(gòu)成。)

思路

既然是判斷能否由子串經(jīng)過(guò)n次重復(fù)得來(lái)，那么就有兩種情況，先看有的情況。
如果字符串s由子串k重復(fù)n次組成，那么s的最后一個(gè)元素一定是k的最后一個(gè)元素。
這個(gè)時(shí)候用循環(huán)依次找出這個(gè)元素位于s的下標(biāo)i，然后構(gòu)成假設(shè)的子串k，再?gòu)南聵?biāo)i+1處，循環(huán)判斷s的剩余部分是否和k對(duì)應(yīng)。

如果能對(duì)應(yīng)，直接返回true，如果不能，那么繼續(xù)找子串k，直到子串k等于s。如果還沒(méi)有找到k，那么返回false

代碼

/**
重復(fù)的子字符串

既然是判斷能否由子串經(jīng)過(guò)n次重復(fù)得來(lái)，那么就有兩種情況，先看有的情況。
如果字符串s由子串k重復(fù)n次組成，那么s的最后一個(gè)元素一定是k的最后一個(gè)元素。
這個(gè)時(shí)候用循環(huán)依次找出這個(gè)元素位于s的下標(biāo)i，然后構(gòu)成假設(shè)的子串k，再?gòu)南聵?biāo)i+1處，循環(huán)判斷s的剩余部分是否和k對(duì)應(yīng)。

如果能對(duì)應(yīng)，直接返回true，如果不能，那么繼續(xù)找子串k，直到子串k等于s。如果還沒(méi)有找到k，那么返回false
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function (s) {
    var base = '';
    var lastWord = s[s.length - 1];
    for (var i = 0; i < s.length; i++) {
        if (i == s.length - 1) {
            return false;
        }
        if (s[i] == lastWord) {
            base = s.slice(0, i + 1);
            if (s.length % base.length != 0) {
                continue;
            }
            var flag = true;
            for (var j = 0; j < s.length; j++) {
                if (s[j] != s[j % base.length]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return true;
            }
        }
    }
    return false;
};

回到目錄