2017-10-29 @sunderls
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.
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.
/**
* @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