Leetcode 459:重复的子字符串(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 459:重复的子字符串(超详细的解法!!!)

in leetcode with 0 comment

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

示例 1:

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

示例 2:

输入: "aba"
输出: False

示例 3:

输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

解题思路

首先思考暴力解法,枚举所有可能的子串长度,然后判断所有的子串是不是满足条件即可。

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        t = n // 2
        while t >= 1:
            if n % t == 0:
                st = s[:t]
                for i in range(t, n - t + 1, t):
                    if s[i:i + t] != st:
                        break
                else:
                    return True
            t -= 1
        return False

这样做当然不够优秀。这个问题可以使用KMP算法(超详细!!!)来求解。我们知道在KMP算法中,通过计算next数组可以知道前后缀的最大匹配长度。假设$next[i-1]=j_0$,那么由next数组的定义可知$s[:j_0]=s[i-j_0:i]$。

更一般的,如果我们能够找到一个$k$,使得对于所有小于$k$的$k_0$,都有$s[j_{k_0}]!=s[i]$且$s[j_k]=s[i]$,那么$next[i]=j_k+1$,否则进一步回归$j_{k+1}=next[j_k]$。对于字符串s,如果$j$满足$1\leq j \leq n$且$s[:j]=s[n-j:n]$,令$k=n-j$,如果$k | n$,假设$n=mk$,那么$s[:(m-1)k]=s[k:mk]$,那么s满足条件。最后代码非常简单,只需计算next数组,然后判断能否整除即可。

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        f = [0] * (n + 1)
        f[0], i, j = -1, 0, -1
        while i < n:
            while j != -1 and s[j] != s[i]:
                j = f[j] 
            i += 1
            j += 1
            f[i] = j
        return f[-1] and n % (n - f[-1]) == 0

这个问题还有一个更加简洁的方法,我们知道如果一个字符串包含重复子串,我们假设重复子串为x,那么s=nxs+s=2nx。此时如果去掉s+s的首末字符,那么此时(s+s)[1:-1]中包含(2n-2)x个重复子串。如果(s+s)[1:-1]包含x的话,那么(2n-2)x>=nx,即n>=2;否则(s+s)[1:-1]不包含x,可以推出0<n<2,即n==1

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return s in (2 * s)[1:-1]

reference:

https://leetcode.com/problems/repeated-substring-pattern/discuss/94334/Easy-python-solution-with-explaination

https://blog.csdn.net/u010983881/article/details/71204644

https://leetcode-cn.com/problems/repeated-substring-pattern/solution/guan-yu-gou-zao-ssjin-xing-pan-duan-de-zheng-ming-/

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses