28 - 实现 strStr() - implement-strstr

[TOC]

一、题目

实现 strStr() 函数。

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

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

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

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

二、解法

2.1 暴力解法

var strStr = function (haystack, needle) {
    // 1.特况
    if (!needle) return 0
    // 2.一般
    let len = haystack.length
    let nLen = needle.length
    // 一个指针指向needle,一个指针指向haystack
    let i = 0
    for (let j = 0; j < len; j++) {
        if (haystack[j] === needle[i]) {
            i++
            if (i === nLen) return j - nLen + 1
        } else {
            j = j - i
            i = 0
        }
    }
    return -1
};

2.2 KMP算法

• 部分匹配值 = “前缀” 和 “后缀" 的最长的共有元素的长度。
• 移动位数 = 已匹配的字符数-对应的部分匹配值。
• 无须回退，效率高。典型的牺牲空间换取时间的算法。

2.2.1 部分匹配算法

var kmpGetPartMatchLen = function (str) {
    let partMatch = []
    for (let i = 0; i < str.length; i++) {
        let prefix = '',
            suffix = ''
        let newStr = str.slice(0, i + 1)
        // 判断前后缀是否相同
        for (let j = 0; j < i; j++) { // i 即子串长度
            prefix = newStr.slice(0, j + 1)
            suffix = newStr.slice(-j - 1) // [倒数第0个,倒数第j+1个)
            if (prefix === suffix) {
                partMatch[i] = prefix.length
            }
        }
        // 最终都不存在匹配
        partMatch[i] = partMatch[i] || 0
    }
    return partMatch
}

2.2.2 移动位数算法

• 以haystack为参照，needle向前移动。

let moveLen = matchedLen - partMatch[matchedLen]

2.2.3 算法实现

• 也许还能优化，以后再看。

var strStr = function (haystack, needle) {
    if (!needle) return 0
    if (haystack === needle) return 0
    if (needle.length >= haystack.length) return -1
    let partMatch = kmpGetPartMatchLen(needle)
    partMatch[-1] = 0
    let len = haystack.length
    let nLen = needle.length
    let matchedLen = 0 // 匹配的长度
    for (let i = 0; i < len; i++) {
        if (haystack[i] === needle[matchedLen]) {
            matchedLen++
            if (matchedLen === nLen) return i - nLen + 1
        } else {
            if (matchedLen) i--;
            matchedLen = partMatch[matchedLen - 1]
        }
    }
    return -1
};