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


  • 0
    D

    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++ )
                j++;
            
            if( j == strlen( needle ) )
                return i;
        }
        
        return -1;
    }
    

  • 0
    H

    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.