題目描述

給定一個(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)成。)

很明顯這里所說(shuō)的子串不包括自身

普通解法

以 s 表示給出的非空字符串，若 s 可由自身的子字符串重復(fù)構(gòu)成，則子字符串長(zhǎng)度最少為 1，最長(zhǎng)為 len(s)//2

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        i,l=1,len(s)
        while i<=l//2:
            if l%i==0 and s[:i]*(l//i)==s:
                return True
            i+=1
        return False

簡(jiǎn)潔解法

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return (s+s)[1:-1].find(s) != -1

初次看到這種寫(xiě)法，覺(jué)得真是太簡(jiǎn)潔以至于有點(diǎn)莫名其妙，想了一下才覺(jué)得提交人真的很聰明

以 s 表示給出的非空字符串，以 n 表示其子字符串，如果 n 存在，則 n 的長(zhǎng)度最小為 1，重復(fù)次數(shù)最小為 2。

不妨以 len(n) 表示取字符串 n 長(zhǎng)度，num(s,n) 表示 s 中 n 重復(fù)的次數(shù)。

證明若 n 存在，則 (s+s)[1:-1].find(s) != -1

取極限情況，即 len(n) 為 1，num(s,n) 為 2，則 num(s+s,n) 為 4，num(s+s[1:-1],n) 為 2，num(s+s[1:-1],s) 為 1，則有 (s+s)[1:-1].find(s) != -1 成立。

取一般情況，len(n)>1，num(s,n) 為 m(m>=2)，則 num(s+s,n) 為 2m，num(s+s[1:-1],n) 為 2m-2，num(s+s[1:-1],s) 為 2-(2/m)，因?yàn)?m>=2，則有 (s+s)[1:-1].find(s) != -1 成立。

證明若 (s+s)[1:-1].find(s) != -1，則 n 存在

反證法：假設(shè) (s+s)[1:-1].find(s) != -1，且 n 不存在。

若 (s+s)[1:-1].find(s) != -1，以 x 表示 s 尾部匹配 s 頭部的字符串長(zhǎng)度。

若 len(s)%x==0，則有 s[-x:]==s[:x]==s[x:2*x]...==[-x:]，即 s 的重復(fù)子字符串為 n:s[:x]，即 n 存在；
若 len(s)%x!=0，則令 x=len(s)%x，若 len(s)%x==0，根據(jù)上一條推論，存在 n:s[:x]，若 len(s)%x!=0，則令 x=len(s)%x，遞歸執(zhí)行，極限條件為 x 為 1，即 s 由同一個(gè)字符重復(fù)構(gòu)成。因此若 (s+s)[1:-1].find(s) != -1，則 n 存在。