leetcode with python:459. Repeated Substring Pattern

题目:

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

给定一字串,判断其是否由一重複字串组成
ex:input:"abab"=>output:True
explanation: It is the substring "ab" twice.

我採取我当下最直观的作法

class Solution:    def repeatedSubstringPattern(self, s: str) -> bool:        for i in range(1,len(s)//2+1):            if len(s)%i:                continue                            if s[:i]*(len(s)//i)==s:                return True                    return False

若该字串符合题目条件
则从第一项开始的长度为1~(len(s)//2+1)的子字串中(重複字串长度不可能超过原字串的一半)
其中有一个就是题目要的重複字串

于是我们将其一个一个拿出来验证
先看子字串长度能否整除原字串
因为能整除原字串该子字串才有可能是组成原字串的重複字串

接着看将该子字串重複至和原字串一样长看两者是否相等
若相等直接回传True,反之则继续看下个可能
如果这些可能都不符合期待的话,回传False
最后执行时间51ms(faster than 84.36%)

另一个解法是在讨论区看到的
我认为十分巧妙,所以特别分享一下

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

将一个s去头,一个s去尾,两者结合
若该新字串中存在s,则s为一重複字串组成

这解法似乎还有证明,我大概用实例讲一下
假设一字串a,而aa就是符合题目期待的字串模式
我们将两aa相连去头去尾,假设a去头为b,去尾为c
则新字串变为baac,可以发现aa存在于其中
这方法套用在验证其他形式的以重複字串组成字串也一样行得通
最后执行时间35ms(faster than 97.55%)

那我们下题见