LeetCode

LeetCode-28 实现strStr()

nkul · 9月30日 · 2020年 · 36次已读

本题利用暴力做法,比较简单!

class Solution {
public:
    //本题可以使用kmp算法,待完成!!!
    int strStr(string haystack, string needle) {
        int h = haystack.size() , n = needle.size();
        if(n == 0) return 0;
        for(int i = 0 ; i < h - n + 1; i ++){
            int j = 0 , k = i;
            while(k < h && j < n  && haystack[k] == needle[j]) k++,j++;
            if(j == needle.size()){
                return i;
            }
        }
        return -1;

    }
};

处理有几个特殊点:

1、needel为空,直接返回0

2、对haystack的遍历只需要到h - n + 1即可

3、时间复杂度O(mn)

关于字符串模式匹配,有专门的算法KMP

https://www.zhihu.com/question/21923021


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!