平時使用的一些基本函數,我們只知道他的作用,很少去思考他內部的實現。
今天我們一起探索一下 strStr 函數的實現方式。
題目正文
實現 strStr() 函數。
給定一個 haystack 字符串和一個 needle 字符串,在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從0開始)。如果不存在,則返回 -1。
示例 1:
輸入: haystack = "hello", needle = "ll" 輸出: 2
示例 2:
輸入: haystack = "aaaaa", needle = "bba" 輸出: -1
說明:
當 needle 是空字符串時,我們應當返回什麼值呢?這是一個在面試中很好的問題。
對於本題而言,當 needle 是空字符串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。
解題思路
題目意思很簡單,其實第一句話就足夠了,即實現strStr() 函數。
一下子就能想到可以用遍歷的方式來實現。
錯誤解答
/** * @param {string} haystack * @param {string} needle * @return {number} */ var strStr = function(haystack, needle) { if(needle === ''){ return 0; } var n = 0; for(var i = 0; i < haystack.length; i++){ if(haystack[i] === needle[n]){ n++; if(n === needle.length){ return i - n + 1; } }else{ n = 0; } } return -1; };
這個解法可以看一下,是我第一下想出來的一個 O(n)的邏輯,不過在運行時發現計算結果不對。於是放棄了O(n)的邏輯。
解答
/** * @param {string} haystack * @param {string} needle * @return {number} */ var strStr = function(haystack, needle) { if(needle === ''){ return 0; } var n = 0; for(var i = 0; i < haystack.length; i++){ if(haystack[i] === needle[n]){ n++; if(n === needle.length){ return i - n + 1; } }else{ i = i - n; n = 0; } } return -1; };
略微調整了一下else裡的邏輯,正常通過了運算,這個算法的複雜度在極端情況下,接近 O(n*m),如果有更好的方法,歡迎討論。