28.实现 strStr() (Easy)*

题目描述*

实现 strStr() 函数。

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

说明*

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

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

代码*

字符串匹配，有一堆 nb 的算法，比如 KMP 什么的，但并不会用。题目的标签有双指针，试一下。

题解里看到一种比较容易理解的 Sunday 算法：

源字符串 src，模式字符串 pattern，当前查询索引 index，待匹配字符串 src[idx:idx + pattern.length()]。

每次匹配都会从源字符串中提取待匹配字符串与模式串进行匹配，如果不匹配，则查看待匹配字符串的后一位字符 c，若 c 存在于 pattern 中，则 index = index + offset[c]。

偏移表是存储每一个在模式串中出现的字符，在模式串中出现的最右位置到尾部的距离 + 1。

双指针Sunday

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

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.length() == 0) {
            return 0;
        } 
        if(needle.length() > haystack.length()) {
            return -1;
        }
        unordered_map<char, int> offsetMap;
        int patLen = needle.length(), srcLen = haystack.length();
        for(int i = patLen - 1; i >= 0; i--) {
            if(offsetMap.count(needle[i]) == 0) {
                offsetMap[needle[i]] = patLen - i;
            }
        }
        int index = 0;
        while(index + patLen <= srcLen) {
            string cut = haystack.substr(index, patLen);
            if(cut == needle) {
                return index;
            }else {
                if(index + patLen >= srcLen) {
                    return -1;
                }
                char c = haystack[index + patLen];
                if(offsetMap.count(c)) {
                    index += offsetMap[c];
                }else {
                    index += patLen + 1;
                }
            }
        }
        return -1;
    }
};

最后更新: July 23, 2022