LeetCode《初級演算法》字串之實現strStr() -- JavaScript

語言: CN / TW / HK

題目

題目連結:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnr003/

image.png


題解


題目是字串匹配,資料結構的經典題型,一般教材上都會提供兩種演算法,BF 解法 和 KMP 解法;

1、暴力(BF)解法

```js /* * @param {string} haystack * @param {string} needle * @return {number} / var strStr = function(haystack, needle) {

const hLen = haystack.length,
    nLen = needle.length;

if(nLen === 0) {
    return 0;
}
if(nLen <= hLen) {

    let i = j = 0;
    while(i < nLen && j < hLen) {

        if(haystack[j] === needle[i]) {
            i++;
            j++;
        }else {
            j = j - i + 1;
            i = 0;

        }

    }
    if(i === nLen) {
        return j - i;
    }
}
return -1;

}; ```


2、KMP 解法

kmp 的原理是利用子串的特性(字首和字尾有多少相等,演算法中表現為 next 陣列),使指向主串的指標不用回溯, kmp 的重點: * 理解子串的 next 陣列的含義和求 next 陣列; * 匹配時指向子串的下標應該怎樣利用 next 陣列變換;

```js /* * @param {string} haystack * @param {string} needle * @return {number} / var strStr = function(haystack, needle) {

let hLen = haystack.length;
let nLen = needle.length;
if(nLen > hLen) {
    return -1;
}
if(nLen === 0) {
    return 0;
}
let next = new Array(nLen).fill(0); // 使用fill構造一個數組


// 求 next 陣列
for(let i = 1;i < nLen;i++) {


    for(let m = 1;m <= i;m++){
        let n = 0;
        let nex = 0;
        while((m + n)<=i && needle[n] === needle[m+n]) { // 使用 m+n , 而改變 m
            n++;
            nex++;
        }
        if((m + n) > i) {
            next[i] = nex;
            break; // 記住要break
        }
    }

}




// 匹配字串
let j = 0;

for(let i = 0;i < hLen;i++) { // 這裡是小於 hLen,因為完全有可能出現 hLen-nLen < i < hLen 的一輪迴圈

    let flag = 0;
    while(j < nLen) {
        if(haystack[i] === needle[j]) {
            i++;
            j++;
            flag = 1;
        }else {
            break;
        }
    }


    if(nLen === j) {
        return i - j;
    }else if(0 === j) { // 處理 j === 0 時,訪問 next[j] 越界問題;
        continue;
    }else {

        j = next[j-1]; // 匹配的重點,藉助 next 陣列改變子串的下標 j,而不用回溯主串下標 i

        i--; // 重點,如果到了這裡一定是要把 i 減 1,以保持下一輪還是和這個為匹配的 haystack[i] 比較


    }
}
return -1;

}; ```


3、直接用 JS 提供的 API

這是一個非常快捷,並且會使程式時空複雜度非常低的方法;

因為那些 JS 引擎都是大神搞出來的,他們一般都是以最優的演算法去實現 JS 的 api;

但是如果是學習演算法和練習演算法的話並不推薦這樣做,因為這樣並不能使我們的演算法能力得到提高;

```js var strStr = function(haystack, needle) {

return haystack.indexOf(needle);

}; ```


大家如果有更好的思路和解法,歡迎大家一起來討論啊~


這是使用 JavaScript 對 LeetCode《初級演算法》的每道題的總結和實現的其中一篇,彙總篇在這裡:

https://juejin.cn/post/7006692002125316103