本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-07(10)

2020-08(50)

(力扣每日一题)重复的子字符串

发布于2020-08-27 07:36     阅读(825)     评论(0)     点赞(27)     收藏(0)



重复的子字符串

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
在这里插入图片描述
解题思路
方法一 枚举法
1、如果一个长度为 n 的字符串 s可以由它的一个长度为 n’的子串 s’重复多次构成,那么:
n 一定是 n’ 的倍数;s ′ 一定是 s 的前缀;
2、对于任意的 i∈[n ′,n),有 s[i]=s[i−n′]
也就是说,s 中长度为 n’ 的前缀就是 s’,并且在这之后的每一个位置上的字符 s[i],都需要与它之前的第 n’个字符 s[i−n′] 相同。
3、因此,我们可以从小到大枚举 n’,并对字符串 s进行遍历,进行上述的判断。

代码

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1, n // 2 + 1):
            if n % i == 0:
              #对于任意的 i∈[n ′,n),有 s[i]=s[i−n′]。  
                if all(s[j] == s[j - i] for j in range(i, n)):
                    return True
        return False

时间复杂度:O(n^2),其中 n是字符串 s 的长度。
空间复杂度:O(1)。

方法二 字符串匹配
在这里插入图片描述

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return (s + s).find(s, 1) != len(s)

方法三 (KMP算法)(困难)
KMP算法学习参考:https://www.cnblogs.com/BlackString/p/13175632.html

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        def kmp(query: str, pattern: str) -> bool:
            n, m = len(query), len(pattern)
            fail = [-1] * m
            for i in range(1, m):
                j = fail[i - 1]
                while j != -1 and pattern[j + 1] != pattern[i]:
                    j = fail[j]
                if pattern[j + 1] == pattern[i]:
                    fail[i] = j + 1
            match = -1
            for i in range(1, n - 1):
                while match != -1 and pattern[match + 1] != query[i]:
                    match = fail[match]
                if pattern[match + 1] == query[i]:
                    match += 1
                    if match == m - 1:
                        return True
            return False
        
        return kmp(s + s, s)

时间复杂度:O(n),其中 n 是字符串 s 的长度。
空间复杂度:O(n)。

原文链接:https://blog.csdn.net/Nakisha/article/details/108203886






所属网站分类: 技术文章 > 博客

作者:丸子

链接:https://www.pythonheidong.com/blog/article/496021/aeab987081df650d5088/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

27 0
收藏该文
已收藏

评论内容:(最多支持255个字符)