leetcode-28:实现 strStr()(字符串匹配,暴力匹配算法和KMP算法)

简介: leetcode-28:实现 strStr()(字符串匹配,暴力匹配算法和KMP算法)

题目:

题目链接

实现 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解释,0基础可以先看这个链接

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=2i为最后那个“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;
    }
};


相关文章
|
3天前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
16 1
|
17天前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
22 9
|
17天前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
13 0
|
17天前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
26 0
|
17天前
【LeetCode 21】28. 实现 strStr()
【LeetCode 21】28. 实现 strStr()
29 0
|
17天前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
14 0
|
17天前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
14 0
|
17天前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
17 0
|
17天前
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
13 0
|
3天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。