Day 09 | 28.实现 strStr()

Leetcode 28.实现 strStr()

题目：28.实现strStr() 讲解： https://www.bilibili.com/video/BV1PD4y1o7nd

初始思路

考点是KMP算法。

代码

// 暴力算法
var strStr = function (haystack, needle) {
    const needleLength = needle.length;
    const len = haystack.length
    // 当 needle 是空字符串时我们应当返回 0
    if (needleLength === 0) return 0;
    for (let i = 0; i < len; i++) {
        let j = 0;
        while (i + j < len && haystack[i + j] === needle[j]) {
            j++;
        }
        // 如果针对needle的指针到达了末尾，就认为匹配成功
        if (j === needleLength) {
            return i;
        }
    }
    // 如果不存在就返回-1
    return -1;
};

// KMP算法
var strStr = function (haystack, needle) {
    const n = haystack.length, m = needle.length;
    const next = new Array(m).fill(0);
    // 计算前缀表
    for (let i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle[i] !== needle[j]) {
            j = next[j - 1];
        }
        if (needle[i] === needle[j]) {
            j++;
        }
        next[i] = j;
    }
    // 根据前缀表进行匹配
    for (let i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] === needle[j]) {
            j++;
        }
        if (j === m) {
            return i - m + 1;
        }
    }
    return -1;
};

感想

1. 看得云里雾里，求前缀的部分没看懂。再多看看。。。