Python Boyer–Moore string search algorithm (32ms, 89%)


  • 0
    L

    class Solution(object):
    def strStr(self, haystack, needle):

        if len(haystack) == 0 and len(needle) == 0:
            return 0
        elif len(haystack)<len(needle):
            return -1
        elif len(haystack) > 0 and len(needle) == 0:
            return 0
        
        bad_table = {}
        len_needle = len(needle)
        moving_len_needle = len(needle)
        for i in range(0,len_needle-1):
            bad_table[needle[i]]= len_needle-1-i
        
        if needle[-1] not in bad_table:
            bad_table[needle[-1]]=len_needle
                
        ncount = -1
        index = 0
        
        
        while index<=(len(haystack)-len(needle)):
            while needle[ncount] == haystack[moving_len_needle+index-1]:
                if ncount == -len(needle):
                    return index
                else:
                    ncount -= 1
                    moving_len_needle -= 1
            
            if haystack[len_needle-1+index] in bad_table:
                index = bad_table[haystack[len_needle-1+index]] +index
            else:
                index = len_needle +index
                
            ncount = -1
            moving_len_needle = len(needle)
        return -1

Log in to reply
 

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