題目

難度：★☆☆☆☆
類型：數(shù)組

給定一個非空的字符串，判斷它是否可以由它的一個子串重復多次構成。給定的字符串只含有小寫英文字母，并且長度不超過10000。

示例

示例 1:
輸入: "abab"
輸出: True
解釋: 可由子字符串 "ab" 重復兩次構成。

示例 2:
輸入: "aba"
輸出: False

示例 3:
輸入: "abcabcabcabc"
輸出: True
解釋: 可由子字符串 "abc" 重復四次構成。 (或者子字符串 "abcabc" 重復兩次構成。)

解答

這里我們觀察到一個現(xiàn)象，對于一個字符串s，我們將兩個該字符串連接成一個更長的字符串（s_double），該字符串中至少包含兩個s子串，如果s可以由多個重復單元構成，那么合并后的字符串中一定包含超過兩個s子串（可重疊），例如，兩個"abab"組成的"abababab"中包含3個"abab"，而兩個"aba"組成的"abaaba"則只包含兩個"aba"，根據(jù)這個原理，我們只需要統(tǒng)計s+s中s（可重疊）出現(xiàn)的次數(shù)，并與2比較即可。

這里為了簡化計算，我們把s+s的首尾兩端字符去掉，這樣就只需要查看s是否在剩余的字符串中即可。編碼時通過索引范圍[1:len(s)*2-1]起到去掉首尾兩端字符的效果。

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s in (s+s)[1:len(s)*2-1]

如有疑問或建議，歡迎評論區(qū)留言~