题目:
实现 strStr() 函数
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll" 输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba" 输出: -1
解题:
python 里面有个find()函数,可以直接查找匹配的字符串,并返回索引,这边不用这种方法。
方法一:暴力匹配算法
class Solution: def strStr(self, haystack: str, needle: str) -> int: hlen = len(haystack) nlen = len(needle) i,j = 0,0 while i<hlen and j<nlen: if haystack[i]==needle[j]: i+=1 j+=1 else: i = i-j+1 j=0 if j == nlen: return i-j else: return -1
方法二:KMP算法
KMP算法相比暴力匹配算法改进了什么呢?
它创建了Next数组,再遍历一遍需要被匹配的字符串,所以时间复杂度为O(m+n),而暴力匹配算法时间复杂度为O(mn)。
暴力匹配算法,在每次匹配结束后,被匹配的字符串索引需要i = i-j+1 回溯,匹配的模板字符串需要变成j=0,然而,有了KMP算法,被匹配的字符串,索引不需要回溯,匹配的模板字符串索引也不用j=0开始,
这样子在字符串匹配过程中时间复杂度为O(n),创建next列表时 时间复杂度为O(m),总共时间复杂度为O(m+n)。
python解法
class Solution: def strStr(self, haystack: str, needle: str) -> int: m = len(needle) index = 0 i = 1 pnext = [0]*m while i<m: if needle[index]==needle[i]: pnext[i]=index+1 i+=1 index+=1 elif index!=0: index = pnext[index-1] else: i+=1 m = len(needle) n = len(haystack) i,j = 0,0 while i<m and j<n: if needle[i]==haystack[j]: i+=1 j+=1 elif i!=0: i = pnext[i-1] else: j+=1 if i==m: return j-i else: return -1
说一下创建next过程
可能index = pnext[index-1]
会有所疑惑,这一步骤是为了获得上一个字母已经匹配到字符串的索引(这样就不需要回溯i
了,index
也不需要归为0,然后重新开始匹配了(虽然只是在创建next,但已经用到了KMP的核心思想了))
比如:
haystack = "aaaaabbabbbaaabb" needle = "bbaaaaabbabbb" >>[0, 1, 0, 0, 0, 0, 0, 1, 2, 3, 1, 2, 2] #得到的pnext
可以看到每次并不都是0、1、2、3…这样开始。正是因为每次不是这样开始,才使得该算法效率高。
当index=2
,i
为最后那个“b”
的索引时候,发现pnext[index]!=pnext[i]
,于是index = pnext[index-1]
得到的index=1
,发现pnext[index]==pnext[i]
,于是pnext[i]=index+1
为2,所以pnext
最后一个值为2。
可以发现:
创建next过程中,是字符串后面部分和前面部分匹配,而两个字符串匹配时候,是两个串之间比。
c++解法
class Solution { public: vector<int> create_pnext(string needle){ int m=needle.size(); int index=0; int i=1; vector<int> pnext(m); while(i<m){ if(needle[index]==needle[i]){ pnext[i]=index+1; index++; i++; } else if(index!=0){ index=pnext[index-1]; } else{ i++; } } return pnext; } int strStr(string haystack, string needle) { vector<int> pnext=create_pnext(needle); int m=haystack.size(); int n=needle.size(); int i=0,j=0; while(i<m&&j<n){ if(haystack[i]==needle[j]){ i++; j++; } else if(j!=0){ j=pnext[j-1]; } else{ i++; } } if(j==n) return i-j; return -1; } };
方法三:内置函数
c++解法
class Solution { public: int strStr(string haystack, string needle) { if(needle.empty()) return 0; int pos=haystack.find(needle); if(pos==-1) return -1; return pos; } };