LeetCode 28 Implement strStr()

LeetCode 2022-02-20 13:28:25 2022-02-20 15:43:21 212 次浏览

概述

https://leetcode.com/problems/implement-strstr/

暴力法

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle == "") return 0;
        for (int i = 0; i < haystack.size(); i ++) {
            int k = i;
            int j = 0;
            for (; j < needle.size() && k < haystack.size(); j ++, k ++) {
                if (haystack[k] != needle[j]) break;
            }
            if (j == needle.size()) {
                return i;
            }
        }
        return -1;
    }
};

O(mn) 的时间复杂度,TLE 了。

离谱,下面这个就过了:

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.length()==0) return 0;
        if(haystack.length()<needle.length()) return -1;
        for(int i=0;i<=haystack.length()-needle.length();i++){
            if(haystack[i]==needle[0]){
                bool flag = true;
                for(int j=1;j<needle.length();j++){
                    if(haystack[i+j]!=needle[j]){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    return i;
                }
            }

        }
        return -1;
    }
};

而我参照改进的就没过:

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle == "") return 0;
        if (needle.size() > haystack.size()) return -1;
        for (int i = 0; i <= haystack.size() - needle.size(); i ++) {
            int k = i;
            int j = 0;
            for (; j < needle.size() && k < haystack.size(); j ++, k ++) {
                if (haystack[k] != needle[j]) break;
            }
            if (j == needle.size()) {
                return i;
            }
        }
        return -1;
    }
};

头一次见:80 / 80 test cases passed, but took too long.

这道题标的简单啊喂!

KMP 字符串匹配算法

https://labuladong.gitee.io/algo/3/26/101/

KMP 算法永不回退 txt 的指针 i,不走回头路(不会重复扫描 txt), 而是借助 dp 数组中储存的信息把 pat 移到正确的位置继续匹配, 时间复杂度只需 O(N),用空间换时间,所以我认为它是一种动态规划算法。

http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

大概看懂了,我们首先需要构造一个部分匹配表,其中指示了如果部分匹配到该处,我们要跳转的位置。

里面的项的计算方式:

The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.

使用方式:

If a partial match of length partial_match_length is found and table[partial_match_length] > 1, we may skip ahead partial_match_length - table[partial_match_length - 1] characters.

其实这个想法很简单,就是,当我们遇到一个不匹配的项后,我们可不可以不重置 text 指针,从该不匹配的开始呢? 不能,因为已经匹配的那部分里可能包含新的开始,我们需要找出里面最远的新的开始,开始新的开始。 这就是为什么我们要求最大的。

举例,对于 pattern 字符串 “abababca”,我们计算部分 pattern “ababa” 时,我们有 4 个前缀:(“a”, “ab”, “aba”, and “abab”), 和 4 个后缀:(“a”, “ba”, “aba”, and “baba”),其中 “a” 和 “aba” 都出现了,其中 “aba” 最长,为 3, 所以对应 “ababa” 的值为 3,该部分 pattern 本身长度为 5,5 - 3 = 2,所以当我们只匹配到该部分 pattern 时, 我们可以从旧的开始 + 2 处进行新的开始,可以看到即从 aba 处开始,其显然是一个合法的已匹配部分。

实现可以参考这里: https://leetcode.com/problems/implement-strstr/discuss/12956/C%2B%2B-Brute-Force-and-KMP

未经允许,禁止转载,本文源站链接:https://iamazing.cn/