题目描述
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。
示例 2:
输入: “aba”
输出: False
示例 3:
输入: “abcabcabcabc”
输出: True
解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)
解题思路
- 方法一。遍历所有可能的周期,看该周期下各子串部分是否相等;
- 方法二。将原始的字符串重复一遍,然后去掉头部和尾部的两个元素,看原来的字符串在不在里面。
- 方法三: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) return (pmt_of_s[length - 1] > 0) and (length % (length - pmt_of_s[length - 1]) == 0) def get_pmt(self, pattern): pmt = [0] * (len(pattern) + 1) pmt[0] = -1 i = 0 j = -1 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