LeetCode 28. Implement strStr()

題目

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

翻譯

實做strStr()。

給一個指針needle跟字串堆疊haystack，回傳指針第一次在堆疊中出現的位置index。

範例：
haystack = "abcdede"
needle = "de"，"de"第一次出現的位置為3

思路

1. 這就是字串搜尋的功能，用api的話，只要用String的indexOf(x)就可以直接得到答案
2. 再來是用截字串的方法，haystack(i,needle.length)如果跟needle相等，回傳i的位置即可
3. 如果不用api的情況下，使用迴圈比對haystack跟needle
4. haystack = "abcbb"，needle = "bb" 為例
5. 一開始 abcbb != bb 失敗 ； 往下比對abcbb != bb可是接下來 abcbb != bb 失敗
6. 值到最後abcbb == bb比對成功，回傳haystack現在的位置3
7. 以上寫法效率太差，實際上可以用KMP演算法來增加速度，不過KMP演算法我覺得超出easy的部分，這邊就先跳過不提

解題

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    return haystack.indexOf(needle);
}

截字串比對

var strStr = function(haystack, needle) {
    if(!needle) return 0;
    if(!haystack || needle.length > haystack.length) return -1;

    var i,j;
    for(i = 0 ; i < haystack.length ; i++){
       var str = haystack.substr(i,needle.length);
       if(str == needle){
           return i;
       }
    }

    return -1;
};

超出時間的解題

var strStr = function(haystack, needle) {
    if(!needle) return 0;
    if(!haystack || needle.length > haystack.length) return -1;

    var i,j;
    for(i = 0 ; i < haystack.length ; i++){
       var index = i;
       j = 0; //比對失敗，將haystack指針移向下一個字元，重新跟needle比對
       while(haystack.charAt(index) == needle.charAt(j) ){
           //比對needle跟haystack，比對成功回傳haystack開始比對的位置
           if(j == needle.length -1){
                return parseInt(i);   
           }
           index++; j++;
       }
    }

    return -1;
};