0459-Repeated Substring Pattern

这个系列算是出于个人兴趣开的一个新坑吧，最近看到同学刷LeetCode算法题，就想写写那些可以一行Python代码写出来的题目，因此本专栏的文章的解题方式效率不做保证，只为追求“一行的浪漫”。

题目

题解

简单解释一下题目，给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。本题难度为Easy。

这题的思路很多，可以用KMP算法解决，不过，这里官方题解给了一种有趣的思路，假设重复的子串为 s ′ sprime s′，那么 s s s就可以写成 s ′ s ′ . . . s ′ sprime sprime ... sprime s′s′...s′，且每个子串 s ′ sprime s′的长度为 n ′ nprime n′，有 1 < = n ′ < n 1<= nprime < n 1<=n′

代码

代码实现上其实将两个s拼接到一起并从位置1开始查询，只要查询的结果不是n就实现了从ss[1:len(ss)]的子串搜索。

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

提交的反馈如下。