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月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
4月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
132 1
两个字符串匹配出最长公共子序列算法
|
4月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
48 1
|
4月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
45 2
|
4月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
36 9
|
4月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
33 0
|
4月前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
45 0
|
4月前
【LeetCode 21】28. 实现 strStr()
【LeetCode 21】28. 实现 strStr()
41 0
|
4月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
33 0
|
4月前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
30 0