Leetcode 459. 重复的子字符串

题目描述

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

很明显这里所说的子串不包括自身

普通解法

以 s 表示给出的非空字符串，若 s 可由自身的子字符串重复构成，则子字符串长度最少为 1，最长为 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

简洁解法

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

初次看到这种写法，觉得真是太简洁以至于有点莫名其妙，想了一下才觉得提交人真的很聪明

以 s 表示给出的非空字符串，以 n 表示其子字符串，如果 n 存在，则 n 的长度最小为 1，重复次数最小为 2。

不妨以 len(n) 表示取字符串 n 长度，num(s,n) 表示 s 中 n 重复的次数。

证明若 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)，因为 m>=2，则有 (s+s)[1:-1].find(s) != -1 成立。

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

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

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

若 len(s)%x==0，则有 s[-x:]==s[:x]==s[x:2*x]...==[-x:]，即 s 的重复子字符串为 n:s[:x]，即 n 存在；
若 len(s)%x!=0，则令 x=len(s)%x，若 len(s)%x==0，根据上一条推论，存在 n:s[:x]，若 len(s)%x!=0，则令 x=len(s)%x，递归执行，极限条件为 x 为 1，即 s 由同一个字符重复构成。因此若 (s+s)[1:-1].find(s) != -1，则 n 存在。