☆打卡算法☆LeetCode 28、实现 strStr() 算法解析

举报
恬静的小魔龙 发表于 2022/07/29 00:50:07 2022/07/29
【摘要】 推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875 大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“实现strStr()。”

题目链接:

来源:力扣(LeetCode)

链接:28. 实现 strStr() - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1 。

说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2

  
 
  • 1
  • 2
  • 3
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1

  
 
  • 1
  • 2
  • 3

二、解题

1、思路分析

这个题是经典的字符串单模匹配的模型,可以使用字符串匹配算法解决,本文使用KMP(Knuth Morris Pratt)算法解这道题。

KMP算法的主要逻辑就是,计算next数组,通过循环来对比target与txt字符串。

2、代码实现

代码参考:

public class Solution {
    public int StrStr(string haystack, string needle) {
        if(needle == "") return 0;
        int[] next = GetNext(needle);  //获取next数组
        int i = 0, j = 0;
        while(i < haystack.Length)
        {
            if(haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else
            {
                if(i < haystack.Length)
                {
                    if(j == 0) i++;
                    else j = next[j - 1];  //回溯,KMP之精髓,与next中的回溯同理
                }
            }
            if(j == needle.Length) return i - j;
        }
        return -1;
    }
    public int[] GetNext(string str)
    {
        int[] next = new int[str.Length];
        int i = 1, j = 0;  //i不能等于1,否则无法错位相比
        next[0] = 0;
        while(i < str.Length)
        {
            if(str[i] == str[j])
            {
                j++;
                next[i] = j;
                i++;
            }
            else
            {
                if(j == 0)
                {
                    next[i] = 0;
                    i++;
                }
                else
                {
                    j = next[j - 1];  //回溯
                }
            }
        }
        return next;
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VZiHMjov-1658998876447)(https://p9-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/d422c09980744acc9c267dfdcfd5feb7~tplv-k3u1fbpfcp-watermark.image?)]

3、时间复杂度

时间复杂度 : O(n+m)

其中m是字符串needle的长度,m是字符串haystack的长度。

空间复杂度: O(m)

其中m是字符串needle的长度。

三、总结

有时间可以详细了解一下KMP算法。

文章来源: itmonon.blog.csdn.net,作者:恬静的小魔龙,版权归原作者所有,如需转载,请联系作者。

原文链接:itmonon.blog.csdn.net/article/details/126039121

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。