Clean KMP solution in python


  • 0
    class Solution(object):
        def getNext(self, substr):
            next, j = [0] * len(substr), -1
    
            for i, char in enumerate(substr):
                while j >= 0 and substr[j + 1] != substr[i]:
                    j = next[j]
    
                if i > 0 and substr[j + 1] == substr[i]:
                    j += 1
    
                next[i] = j
            return next
    
        def strStr(self, haystack, needle):
            if not needle:
                return 0
    
            next, j, m = self.getNext(needle), -1, len(needle)
    
            for i, char in enumerate(haystack):
                while j >= 0 and needle[j + 1] != char:
                    j = next[j]
    
                if needle[j + 1] == char:
                    j += 1
    
                if j == m - 1:
                    return i - j
    
            return -1

Log in to reply
 

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