LeetCode 459. 重复的子字符串 | Python
程序员文章站
2022-07-14 07:54:11
...
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
实现结果
欢迎关注
公众号 【书所集录】
上一篇: 移除数组中的重复元素-C语言