平時使用的一些基本函數，我們只知道他的作用，很少去思考他內部的實現。
今天我們一起探索一下 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)，如果有更好的方法，歡迎討論。
分享到:
