My KMP solution in Golang with 3ms


  • 0
    func strStr(haystack string, needle string) int {
    	if len(haystack) < len(needle) {
    		return -1
    	}
    	if len(needle) == 0 {
    	    return 0
    	}
    	next := Next(needle)
    	q := -1
    	index := -1
    	for i := 0; i < len(haystack); i++ {
    		for q > -1 && needle[q+1] != haystack[i] {
    			q = next[q]
    		}
    		if needle[q+1] == haystack[i] {
    			q += 1
    		}
    		if q == len(needle)-1 {
    			index = i-len(needle)+1
    			break
    		}
    	}
    	return index
    }
    
    func Next(s string) []int {
    	next := make([]int, len(s))
    	next[0] = -1
    	k := -1
    	for q := 1; q < len(s); q++ {
    		for k > -1 && s[k+1] != s[q] {
    			k = next[k]
    		}
    		if s[k+1] == s[q] {
    			k += 1
    		}
    		next[q] = k
    	}
    	return next
    }
    

Log in to reply
 

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