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

Implement strStr().

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

analysis

this seems very straightforward, loop through the string and do the matching.

I remembered there is a famous KMP way of doing this much faster, but for now I'll just do it the most tedious way.

code

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    var max = haystack.length - 1 - (needle.length - 1);
    for (var i = 0;i <= max;i++) {
        // try match needle
        var matched = true;
        for (var j = 0; j < needle.length; j++) {
            if (needle[j] != haystack[i + j]) {
                matched = false;
                break;
            }
        }

        if (matched) {
            return i;
        }
    }
    return -1;
};

it passed, ranking top 20%. not so bad, but how can we implement KMP

Tweet