My implementation is to
check chars in [i , i + len(needle)]
if any char in this range (besides the first one) = needle, store that position as k
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 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 else: # print('no match at', i , 'starting at', k) j=0; if k ==0: i = i+1; else: i = k; k=0; if j == len(needle): # print('found complete match') return i - len(needle); return -1;