python-leetcode面试题解之第28题找出字符串中第一个匹配项的下标-python题解.zip

class Solution(object): # def strStr(self, haystack, needle): # """ # :type haystack: str # :type needle: str # :rtype: int # """ # lsh, lsn = len(haystack), len(needle) # if lsn == 0: # return 0 # pos, index = 0, 0 # while index <= lsh - lsn: # if haystack[index] == needle[pos]: # backup = index # while index < lsh and pos < lsn and haystack[index] == needle[pos]: # pos += 1 # index += 1 # if pos == len(needle): # return index - pos # index = backup # index += 1 # pos = 0 # return -1 # def strStr(self, haystack, needle): # lsh, lsn = len(haystack), len(needle) # if lsn == 0: # return 0 # pos, index = 0, 0 # while index <= lsh - lsn: # if haystack[index] == needle[0]: # # slice index:index + lsn # if haystack[index:index + lsn] == needle: # return index # index += 1 # return -1 # KMP # https://discuss.leetcode.com/topic/3576/accepted-kmp-solution-in-java-for-reference/2 def strStr(self, haystack, needle): lsh, lsn = len(haystack), len(needle) if lsn == 0: return 0 next = self.makeNext(needle) i = j = 0 while i < lsh: if j == -1 or haystack[i] == needle[j]: i += 1 j += 1 if j == lsn: return i - lsn if i < lsh and haystack[i] != needle[j]: j = next[j] return -1 def makeNext(self, needle): ls = len(needle) next = [0] * ls next[0], i, j = -1, 0, -1 while i < ls - 1: if j == -1 or needle[i] == needle[j]: next[i + 1] = j + 1 if needle[i + 1] == needle[j + 1]: next[i + 1] = next[j + 1] i += 1 j += 1 if needle[i] != needle[j]: j = next[j] return next