• LeetCode C++ 28.实现strStr()


    题目

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

    说明

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

    示例1:

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

    示例2:

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

    提示

    1 <= haystack.length, needle.length <= 104
    haystack 和 needle 仅由小写英文字符组成

    思路1

    这是我自己做出来的第一道题,不得不说真的很简单。一开始我的想法参考了26题里的string转char,然后再一个个循环对比,但是发现string类型的自带的函数就有查找功能find,它可以实现在一个字符串中搜索另一个字符串,并且返回对应的位置(下标从0开始),就这样题目要求就完成了。还需要注意的就是判断字符串为空有默认的empty()函数,最后再根据条件判断即可。

    class Solution {
    public:
        int strStr(string haystack, string needle) {
            if(needle.empty()){
                return 0;
            }else{
                string m_haystack = haystack;
                string m_needle = needle;
                int t = m_haystack.find(m_needle);
                if(t>=0){
                    return t;
                }else{
                    return -1;
                }
            }
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    思路2

    好吧,看了官方答案,评论区一群人互喷,总之就是不要用内置函数。
    暴力匹配法,我们现在又haystack和needle两个字符串,我们直到needle字符串长度为m,而且它的顺序是不变的,那么我们就再haystack中轮着验证长度为m的字符串是否能和haystack的部分贴合,如果贴合时候有一个贴合失败,就立马返回。

    class Solution {
    public:
        int strStr(string haystack, string needle) {
            int h_size = haystack.size();
            int n_size = needle.size();
            string m_haystack = haystack;
            string m_needle = needle;
    
            for(int i = 0;i + n_size <= h_size;i++){
                bool flag = true;
                for(int j =0; j < n_size;j++){
                    if(m_haystack[i+j] != m_needle[j]){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    return i;
                }
                //加在外面也可以
                if(n_size == 0){
                    return 0;
                }
            }
            return -1;
        }
    };
    
    • 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

    思路3

    KMP算法,上难度了。我只看懂了原理。
    三叶大佬的KMP算法

    class Solution {
    public:
        int strStr(string s, string p) {
            int n = s.size(), m = p.size();
            if(m == 0) return 0;
            //设置哨兵
            s.insert(s.begin(),' ');
            p.insert(p.begin(),' ');
            vector<int> next(m + 1);
            //预处理next数组
            for(int i = 2, j = 0; i <= m; i++){
                while(j and p[i] != p[j + 1]) j = next[j];
                if(p[i] == p[j + 1]) j++;
                next[i] = j;
            }
            //匹配过程
            for(int i = 1, j = 0; i <= n; i++){
                while(j and s[i] != p[j + 1]) j = next[j];
                if(s[i] == p[j + 1]) j++;
                if(j == m) return i - m;
            }
            return -1;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
  • 相关阅读:
    2022谷粒商城学习笔记(二十一)购物车相关功能
    ELK运维文档
    vue 请求php接口 header 传自定义参数 提示cors 跨域问题
    Ribbon 服务调用与负载均衡
    leetcode_208 实现Trie(前缀树)
    【实践篇】Redis最强Java客户端(四)之Ression分布式集合使用指南
    分享一个500页面给大家
    【踩坑专栏】多模块项目boot模块启动后web模块404
    java毕业生设计校园教育服务平台计算机源码+系统+mysql+调试部署+lw
    程序人生,中秋共享
  • 原文地址:https://blog.csdn.net/weixin_42325783/article/details/126152798