GIS与Climate

V1

2022/10/06阅读:20主题:默认主题

day10-重复的字符串

代码随想录(截图自参考【1】)
代码随想录(截图自参考【1】)

本系列是代码随想录算法训练营的学习笔记之day10,主要记录一下刷题的过程,以及核心知识点和一些值的记录的问题。

代码随想录的资源可以看参考链接【1】。

今日知识点

字符串基础:

  • 字符串也是一种数组,在内存上连续分布;

今日题目

  1. 重复的子字符串(459)

给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

  • 按照正常的思路来想可能就是用KMP算法,但是那个对于新手来说确实有点难懂;
  • 在leetcode上看到另外一种思路,感觉太精彩了,那就是如果不可以由该字符串的子串构成,那么拼接两个相同的s,然后用自带的find函数去查找第二个s的起始下标,则下标应该等于len(s);
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return (s + s).find(s, 1) != len(s)

  • 用一行代码就巧解了这个题目,大佬们确实太强了!
  • find(s,1)相当于删除了首字母,这样就不会匹配到第一个原始字符串s了;
  • 如果s可以由子字符串subs组成,则s是有n个subs组成的,s+s就是由2n个subs组成,删除了首字母之后,n个subs组成的子字符串起始位置就只能向后滑动一个subs的长度了!这个思路太强。

KMP的代码如下:

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:  
        if len(s) == 0:
            return False
        nxt = [0] * len(s)
        self.getNext(nxt, s)
        if nxt[-1] != 0 and len(s) % (len(s) - nxt[-1]) == 0:
            return True
        return False
    
    def getNext(self, nxt, s):
        nxt[0] = 0
        j = 0
        for i in range(1, len(s)):
            while j > 0 and s[i] != s[j]:
                j = nxt[j - 1]
            if s[i] == s[j]:
                j += 1
            nxt[i] = j
        return nxt
  • 从长远来说还是要掌握KMP算法,是这类题目的通用解法!

补充知识点

  1. find函数的用法
str.find(str, beg=0, end=len(string))

用于在指定索引范围内查找是否包含子字符串str。

参考

【1】代码随想录:https://programmercarl.com/
【2】https://www.bilibili.com/video/BV1PD4y1o7nd/
【3】https://www.bilibili.com/video/BV1M5411j7Xx/

分类:

后端

标签:

数据结构与算法

作者介绍

GIS与Climate
V1

公众号:GIS与Climate,欢迎关注