JavaScript simple solution in O(n+m)


  • 0
    F

    n being the length of haystack and m the length of needle.

    var strStr = function(haystack, needle) {
        // Initialize sizes
        var n = haystack.length, m = needle.length;
    
        // Edge cases, we cannot find a needle bigger than a haystack
        if (!m) return 0;
        if (m > n) return -1;
    
        for (var i=0; i<n; i++) {
            /* Once we found a matching first character, we add a new loop for each of the following
               If they all match, then this initial position is our solution.
               The special (n-i >= m) optimization help stop early if the needle could not fit in what's
               left of the  haystack*/
            if (haystack[i] === needle[0] && n-i >= m) {
                var ok = true;
                for (var j=1; j<nl; j++) {
                    ok = ok && (haystack[i+j] === needle[j]);
                    if (!ok) break;
                }
                if (ok) return i;
            }
        }
        return -1;
    };
    

  • 0
    C

    why would this be O(m+n), for every position you could check m times, I think it is O(m*n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.