KMP python solution in 14 lines


  • 0
    J

    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):
    		m,n=len(needle),len(haystack)
    		if m==0: return 0
    		if m>n: return -1
    		i,k=0,0
    		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
    			else: 
    				i=k
    				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.