代码随想录算法训练营Day9

28. Find the Index of the First Occurrence in a String

KMP 算法: 专注解决,在一个字符串中,查找是否出现另一个串.

由这三位学者发明的：Knuth，Morris和Pratt，取三位学者首字母,KMP.

核心思想:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,避免从头再去做匹配.

暴力解法O(N*M); KMP解法O(N+M).

class Solution:def strStr(self, haystack: str, needle: str) -> int:# KMP# prefix-suffix tablen = len(haystack)m = len(needle)# 构建 next 数组，数组长度为匹配串的长度next = [0]*mjj = 0for ii in range(1, m):  # ii从1开始while needle[ii] != needle[jj] and jj > 0:jj = next[jj-1]if needle[ii] == needle[jj]:jj += 1# 注意next[ii]的位置next[ii] = jj# Matchingjj = 0for ii in range(n):while haystack[ii] != needle[jj] and jj > 0:jj = next[jj-1]if haystack[ii] == needle[jj]:jj += 1if jj == m: return ii-jj+1return -1# TC: O(N+M)# SC: O(M)

459. Repeated Substring Pattern

KMP的应用

Sol1:移除匹配

拼接s+s, 把首元素和尾元素删除,在其中寻找s.

class Solution:def repeatedSubstringPattern(self, s: str) -> bool:# Sol1: 调用库函数# String.find(s, start, end)# s: substring; start: the start position of string to conduct finding# return (s + s).find(s, 1, -1) != len(s)# Sol2： KMPss = s[1:]+s[:-1]n = len(ss)m = len(s)# Generate prefix-suffix tablenext = [0] * mjj = 0for ii in range(1, m):while s[ii] != s[jj] and jj > 0:jj = next[jj-1]if s[ii] == s[jj]:jj += 1next[ii] = jj# Matchingjj = 0for ii in range(n):while ss[ii] != s[jj] and jj > 0:jj = next[jj-1]if ss[ii] == s[jj]:jj += 1if m == jj: return Truereturn False

字符串总结

要不要使用库函数: 如果库函数仅仅是 解题过程中的一小部分, 并且你已经很清楚这个库函数的内部实现原理的话, 可以考虑使用库函数.

双指针回顾

数学篇,字符串篇,链表篇,N数之和篇

通过前后两个指针不算向中间逼近，在一个for循环下完成两个for循环的工作。

只用双指针法时间复杂度为O(n^{2)，但比哈希法的O(n}2)效率高得多，哈希法在使用两层for循环的时候，能做的剪枝操作很有限。

在双指针法：一样的道理，能解决四数之和 (opens new window)中，讲到了四数之和，其实思路是一样的，在三数之和的基础上再套一层for循环，依然是使用双指针法。

对于三数之和使用双指针法就是将原本暴力O(n^{3)的解法，降为O(n}2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。

同样的道理，五数之和，n数之和都是在这个基础上累加。