28. Implement strStr()

Leetcode

https://leetcode.com/problems/implement-strstr/

題目

Implement strStr().

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

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

解答

• 方法一

var strStr = function(haystack, needle) {
    if(needle === "") return 0;
    
    for(let i=0; i<haystack.length-needle.length+1; i++) {
        let matchIndex = i;
        let j = 0;
        
        while(j < needle.length && haystack[matchIndex] === needle[j]) {
            matchIndex++;
            j++;
        }
        if (j === needle.length) return i;
    }
    return -1;
};

Runtime: 1064 ms, faster than 33.42% of JavaScript online submissions for Implement strStr().

Memory Usage: 41 MB, less than 11.06% of JavaScript online submissions for Implement strStr().

測資

let haystack = "hello", needle = "ll";
haystack = "aaaaa", needle = "bba";
haystack = "", needle = "";

console.log(strStr(haystack, needle));