Penalized for Efficiency?

  • 0

    My implementation is to

    1. check chars in [i , i + len(needle)]

    2. if any char in this range (besides the first one) = needle[0], store that position as k

    3. if all the chars check out, spit out i. if not set i = k

    so basically when doing strStr('ississippi', 'issippi') we'd first start looking at i = 0, then when that fails look at i = 3.

    My annoyance is that while this process would give large speed up in most cases, the checks for the second character makes it slower in others. This means leetcode rejects my code in favor of an algorithm that simply increments i by 1.

    It makes me wish that the online judge accepted a higher range of run times. Am I wrong that my code is better in practice?

            if not haystack and not needle: #if null strings
                return 0
            if not needle:
                return 0
            i =0;
            j =0;    
            k =0;
            while i in range(len(haystack)):
           #     print('checking' , i)
                #k = location of second instance of the first letter of needle
                if haystack[i] == needle[0] and k==0 and j>0:  
                    k = i;
            #        print('second instance at' , k)
                #if match, increment
                if haystack[i] == needle[j] :
            #        print('match at', i)                
                    j = j+1;
                    i = i+1
                #if no match, move to k or if k=0 move to next letter
            #        print('no match at', i , 'starting at', k)
                    if k ==0:
                        i = i+1;
                        i = k;
                if j == len(needle):
             #       print('found complete match')
                    return i - len(needle);
            return -1;

Log in to reply

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