乐趣区

关于leetcode:LeetCode-459-重复的子字符串-Python

459. 反复的子字符串


题目起源:力扣(LeetCode)https://leetcode-cn.com/problems/repeated-substring-pattern

题目


给定一个非空的字符串,判断它是否能够由它的一个子串反复屡次形成。给定的字符串只含有小写英文字母,并且长度不超过 10000。

示例 1:

 输出: "abab"

输入: True

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

示例 2:

 输出: "aba"

输入: False

示例 3:

 输出: "abcabcabcabc"

输入: True

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

解题思路


思路:枚举

先审题,题目中要求某个字符串是否是由某个子串反复屡次形成。

这里咱们假如字符串 cur_string 是由某个子串 sub_string 反复屡次形成。联合示例,尝试剖析外面的法则。

如果依照 sub_string 的长度去划分 cur_string 字符串,这里肯定是可能残缺划分的,也就是说:

  • sub_string 的长度是 cur_string 长度的倍数;
  • 同样的,每个划分局部的子串都是同样的。令 m = len(sub_string),也就说相隔长度 m,前后两个子串对应的字符是雷同的。(后续子串局部同样成立)

如下列图示:

以子串的长度划分给定字符串

相隔长度 m(子串长度),对应的字符雷同

然而这里须要留神,这里反复次数至多有 1 次,那么子串的长度不会大于给定字符串长度的一半。那么咱们枚举的时候,只有在 [1, n/2](n:给定字符串的长度)的范畴内查看是否有符合条件的状况。

那么,依据下面的剖析,当初咱们说下枚举的具体方法(上面局部 n 示意给定字符串的长度):

  • [1, n/2] 开始遍历,先查找能被 n 整除的数字 i;
  • 当找到 i 时,i 也就是此时子串的长度。此时判断子串是否能反复屡次形成给定的字符串。从 [i, n] 开始判断,依据后面剖析的状况二,相隔长度 i(子串长度),对应的字符是雷同的。

具体代码实现如下。

代码实现


class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)

        # 子串至多反复一次
        for i in range(1, n//2+1):
            if n % i == 0:
                if all(s[j]==s[j-i] for j in range(i, n)):
                    return True
        
        return False

实现后果


欢送关注


公众号【书所集录】

退出移动版