Sui Xin's Blog

[LeetCode]459. 重复的子字符串（Repeated Substring Pattern）

Posted on In , Disqus:

题目描述

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过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

Related Posts