KMP python solution in 14 lines

  • 0

    the k means that when partial match failed, we can begin the search from the kth char in the needle string instead of the 1st char.

    class Solution:
    	# @param {string} haystack
    	# @param {string} needle
    	# @return {integer}
    	def strStr(self, haystack, needle):
    		if m==0: return 0
    		if m>n: return -1
    		for j in xrange(n):
    			if i>0:
    				if haystack[j]==needle[k]: k+=1
    				else: k=1 if haystack[j]==needle[0] else 0 #!!!
    			if haystack[j]==needle[i]: i+=1
    				k=1 if i>0 and haystack[j]==needle[0] else 0 #!!!
    			if i==m: return j-m+1
    		return -1

Log in to reply

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