[LeetCode]459. 重复的子字符串(Repeated Substring Pattern)

题目描述

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

示例 1:

输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。

示例 2:

输入: “aba”

输出: False

示例 3:

输入: “abcabcabcabc”

输出: True

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

解题思路

  1. 方法一。遍历所有可能的周期,看该周期下各子串部分是否相等;
  2. 方法二。将原始的字符串重复一遍,然后去掉头部和尾部的两个元素,看原来的字符串在不在里面。
  3. 方法三:KMP。2019 年携程秋招笔试真题,要求用 KMP 算法做,实际上只用到了 PMT 数组的求解,详情见KMP 算法+Python 实现

代码

Python 3.6

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
length = len(s)
for i in range(2, length + 1):
if length % i == 0:
# 没有余数,说明此长度的子串可以构成整串
size = length // i # 该子串的长度
substring = s[:size] # 该子串的内容
for j in range(1, i):
if s[j * size:(j + 1) * size] != substring:
break
else:
return True
return False

执行用时 : 84 ms
内存消耗 : 13.8 MB

方法二

1
2
3
4
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
length = len(s)
return s in (s + s)[1:2 * length - 1]

执行用时 : 52 ms
内存消耗 : 14 MB

方法三:KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
length = len(s)
if length < 2:
return False
pmt_of_s = self.get_pmt(s)
# print(pmt_of_s)
# 最长重复首尾缀是长度的约数,则肯定可以被子串构成
return (pmt_of_s[length - 1] > 0) and (length % (length - pmt_of_s[length - 1]) == 0)

def get_pmt(self, pattern):
# 拿到 PMT 数组
pmt = [0] * (len(pattern) + 1)
pmt[0] = -1
i = 0 # pattern[1:] 的指针
j = -1 # pattern 的指针
while i < len(pattern):
if j == -1 or pattern[i] == pattern[j]:
i += 1
j += 1
pmt[i] = j
else:
j = pmt[j]
return pmt[1:]

执行用时 : 204 ms
内存消耗 : 14.2 MB

参考

https://leetcode-cn.com/problems/repeated-substring-pattern/comments/44823