28. Find the Index of the First Occurrence in a String

Leetcode link

题目简介

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */

题目给了两个数组：haystack 与 needle

要求在 haystack 中找到与 needle 完全匹配的子字符串并返回该子字符串在 haystack 中开头的下标

解题思路

这题我们还是用双指针来分别指向 haystack 与 needle

我们用 i 指针遍历 haystack，needlePtr 指针指向 needle 的第一个元素

如果 haystack[i] === needle[needlePtr] 则我们让两个指针一起前进直到其中一个遇到字符串尾或者两个指针指向的字符不同

如果 needlePtr === needle.length 表示我们遍历完了整个 needle 字符串，我们已经找到一个完全符合的子字符串了

否则我们重新把 needlePtr 指向 needle 的开头（也就是 needlePtr = 0）

需要留意的是，我们还原 needlePtr 的时候需要一并还原指针 i（也就是 i -= needlePtr）否则可能错过重复的字符串

Javascript

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    let needlePtr = 0

    // we can optimize this to i <= haystack.length - needle.length
    for (let i = 0; i < haystack.length; i++) {
        while (i < haystack.length && needlePtr < needle.length && haystack[i] === needle[needlePtr]) {
            i++
            needlePtr++
        }
        if (needlePtr === needle.length) {
            return i - needlePtr
        } else {
            i -= needlePtr
            needlePtr = 0
        }

    }
    return -1
};