easy题记录28

题目描述

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

思路

简单实现

滑动窗口暴力检索，针对haystack的每一位i：往后一位一位地看是否与模式串的对应位匹配，如果某一位对不上就退出。循环完成后检查是否全部匹配上，如果是直接返回i。

Sunday算法

当不匹配时：

检查haystack：如果haystack[i]不在模式串里，直接跳到这个字符的下一位。

如果在，移动时把模式串中最右边的对应字符和haystack[i]对位。一定要取最右，否则可能错过前面的模式。

完整代码

简单实现

function strStr(haystack: string, needle: string): number {
    const hlen = haystack.length;
    const nlen = needle.length;
    let i = 0;
    while(i < hlen - nlen + 1) {
        let idx = 0;
        let j = i;
        
        while(j < hlen && idx < nlen && haystack[j] === needle[idx]) {
            j++;
            idx++;
        }

        if(idx === nlen) return i;
        i++;
    }
    
    return -1;
};

Sunday算法

function strStr(haystack: string, needle: string): number {
    const n = haystack.length;
    const m = needle.length;
    if (m === 0) return 0;
    
    // 偏移表，记录模式串第i位需要对位时跳跃的距离
    const offset = new Array(256).fill(m + 1);
    for (let i = 0; i < m; i++) {
        offset[needle.charCodeAt(i)] = m - i;
    }
    
    let i = 0;
    while (i <= n - m) {
        let j = 0;
        while (j < m && haystack[i + j] === needle[j]) {
            j++;
        }
        
        if (j === m) {
            return i;
        }
        
        // 按偏移表跳跃
        if (i + m >= n) break;
        i += offset[haystack.charCodeAt(i + m)];
    }
    
    return -1;
}