ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

KMP算法(hot150记录)

KMP算法(hot150记录)

文章目录

  • 一、最后一个单词的长度
    • 1.1 题目
    • 1.2 题解
  • 二、最长公共前缀
    • 2.1 题目
    • 2.1 题解
  • 三、找出字符串中第一个匹配项的下标-KMP算法
    • 3.1 题目
    • 3.2 题解
    • 3.2.1 暴力枚举
    • 3.2.2 KMP算法
      • 思路
      • 代码实现
      • 时间和空间复杂度分析

一 只是顺手记录,二 是KMP算法的预热,引入了公共前缀的概念。

一、最后一个单词的长度

1.1 题目

给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例1: 输入:s="Hello World"输出:5解释:最后一个单词是“World”,长度为5。 示例2: 输入:s=" fly me to the moon "输出:4解释:最后一个单词是“moon”,长度为4。

1.2 题解

classSolution:deflengthOfLastWord(self,s:str)->int:# strip() 去除首尾空格,split() 按空格分割成单词列表words=s.strip().split()# 如果字符串全由空格组成,或者为空ifnotwords:return0# 返回最后一个单词的长度returnlen(words[-1])
  • Python 中的 strip() 方法用于移除字符串头尾的空白字符或指定字符序列。默认情况下,它会移除字符串两端的空格和换行符,但你也可以指定其他字符来移除。
  • 使用场景:
    当你需要清理字符串数据,例如从文件中读取的文本,或者在处理用户输入时,strip() 方法非常有用。它能够帮助确保字符串不会因为意外的前导或尾随空白而导致数据处理错误。

二、最长公共前缀

2.1 题目

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。

示例1: 输入:strs=["flower","flow","flight"]输出:"fl"示例2: 输入:strs=["dog","racecar","car"]输出:""解释:输入不存在公共前缀。

2.1 题解

classSolution:deflongestCommonPrefix(self,strs:list[str])->str:# 必须加上这句,防止传入空数组ifnotstrs:return""# 拿出数组中第一个单词first_word=strs[0]# 遍历第一个单词中的字符串foriinrange(len(first_word)):current_letter=first_word[i]# 将第一个单词中的字符与其他单词中对应字符的单词相比forwordinstrs[1:]:ifi==len(word)orword[i]!=current_letter:returnfirst_word[:i]returnfirst_word

三、找出字符串中第一个匹配项的下标-KMP算法

3.1 题目

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。

示例1: 输入:haystack="sadbutsad",needle="sad"输出:0解释:"sad"在下标0和6处匹配。 第一个匹配项的下标是0,所以返回0。 示例2: 输入:haystack="leetcode",needle="leeto"输出:-1解释:"leeto"没有在"leetcode"中出现,所以返回-1。

3.2 题解

3.2.1 暴力枚举

classSolution:defstrStr(self,haystack:str,needle:str)->int:fori,iteminenumerate(haystack):l=len(needle)ifhaystack[i:i+l]==needle:returnireturn-1

3.2.2 KMP算法

人生处于顺境时能走多快不重要,重要的事遭遇挫折时,能够快速找回自己。—— KMP

思路

  1. 首先要明白最长公共前后缀长度意思:比如说:字符串‘AB’的最长公共前后缀是0,‘ABA’的是1,‘ABAB’的是2,‘ABABC’是0,‘ABABCA’是1。
  • 最长公共前后缀长度是指一个字符串的前缀和后缀相同的最大长度。
  • 前缀:字符串从开头开始的连续子串,但不包含整个字符串本身。
  • 后缀:字符串从结尾开始的连续子串,但不包含整个字符串本身。
  1. 对于一个字符串P,我们可以定义一个next数组,next数组的长度等于字符串P的长度,next数组中每个位置存放着字符串P中对应位置长度字符串的 最长公共前后缀长度。例如,字符串P ‘ABABCABAB’的next数组为 [0,0,1,2,0,1,2,1,2]。

  2. 可以说,一个字符串的next数组记录着字符间的重复关系。

  3. 所以,如果一个字符串P=‘ABABC’去和主字符串S=‘ABABABC’匹配时,当P[4]和S[4]失配,这意味着p[0:4] = S[0:4],而‘ABAB’的最长公共前后缀长度是2,这意味着,p[0:4]的前两位和后两位相同,而p[0:4]的后两位等于S[0:4]的后两位,即 p[0:4]的前两位 = S[0:4]的后两位,这几位数不需要重新匹配。所以根据next的信息——也就是字符串本身重复的信息,可以省去一些匹配工作量。

解释一下下图:

  • 字符串P与T匹配时,两个指针i和j,i 指向T,j指向P,向前移动,对应位置相比,当P[4]与T[4]失配时,候我们不需要将指针i回退到T[1]位置,j回退到P[0],逐次前移,依次对比。而只需要看看next数组next[j-1]的数值是多少,数值是2,表明字符串P[0:4]的最大公共前后缀是2(即,这个字符串的后两位和前两位是相同,既然后两位已经和P的对应位置匹配了,那么前两位自然也是匹配的,所以不用比了),所以将指针 j 回退到 P[2]的位置和T[4]相比,继续向前。

代码实现

classSolution:defstrStr(self,haystack:str,needle:str)->int:ifnotneedle:return0# 1. 建 next 数组(lps 长度形式)nxt=[0]*len(needle)# 初始化next数组,第一位肯定是0k=0foriinrange(1,len(needle)):whilekandneedle[k]!=needle[i]:k=nxt[k-1]ifneedle[k]==needle[i]:k+=1nxt[i]=k# 2. 主串匹配j=0fori,chinenumerate(haystack):whilejandch!=needle[j]:j=nxt[j-1]# 让j 退回到最大公共前后缀结束的后一位,这一步和上面构建next数组那里是一致的ifch==needle[j]:j+=1ifj==len(needle):returni-j+1return-1

时间和空间复杂度分析

  • 时间复杂度:建立next数组,遍历一次子串(假设长度为n),主串匹配遍历一次(假设主串长度为m),两次,指针都不回退,时间复杂度为:O(m+n)
  • 空间复杂度:额外开了next数组,长度为子串needle长度一致,空间复杂度为O(n)
返回列表