C solution of O( (n-k)k )

  • 0

    Suppose the length of haystack is n, the length of needle is k, then this algorithm is at worst O( (n-k)k ) in time.
    Intuitively, we start from the first char of haystack, searching through the (n-k)th one, to look for any matches.

        char *h, *n;
        int i, j;
        for( i = 0; i <= (int)strlen( haystack ) - (int)strlen( needle ); i++ ) {
            h = haystack + i;
            n = needle;
            j = 0;
            while( j < strlen( needle ) && *h++ == *n++ )
            if( j == strlen( needle ) )
                return i;
        return -1;

  • 0

    This solution will overlook a question about when the size of haystack is less than the size of needle.For example ,haystck is "abb",needle is "abaaa". I think you should add a code like if(strlen(haystack)<strlen(needle) return -1;
    thank you for your consideration.

Log in to reply

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