未分類

Implement strStr()

Go, LeetCode, String, TwoPointers

Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

提示 解題應用
TwoPointers KMP演算法
String 規律觀查

Default:

1
2
3
func strStr(haystack string, needle string) int {
}

解答思路:

這題是實作c語言中常用到的字串搜尋strStr()，很明顯的就是要我們實作KMP演算法，也就是先將要搜尋的字串轉為前綴的相似表，接著主字串才依這個表來加速比對，由於需要一步步推倒，建議可以看看GO社群中有人整理好關於KMP演算法的文章[TIL] 有關字串搜尋的演算法: KMP，至於KMP的實作你可以參考文章上的範例或者像這邊則是用我自已覺得比較易懂的方式來實作出來。

程式碼解說:

一開始要先取得搜尋字串的相似表，接著主字串才依這個表來加速比對，主字串與要搜尋的字串同時遍歷的關係，任一字串到底便結束便利，當主字串的字母與搜尋字串的字母相同則共同往下移，如果要比對的字串在第一個字母就不相同，此時便只位移主字串即可，而如果比對到一半不相同但前綴有相似的部分，就對照相似表將搜尋字串比對到的位置往前移到前綴相似的地方以繼續與主字串那次判斷(主字串便不需回流以加速比對速度)，最後在比對結束後如果搜尋字串的index位置超過範圍(index與長度相同)，表示在主字串中包含了要搜尋字串，主字串在比對完時index的位置與搜尋字串的長度相減，此值就是搜尋字串在主字串的開頭位置並做回傳，否則不包含就回傳-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func strStr(haystack string, needle string) int {
	var i int
	var j int
	table := prefix(needle)
	for i < len(haystack) && j < len(needle) {
		if haystack[i] == needle[j] {
			i++
			j++
		} else if j == 0 {
			i++
		} else {
			j = table[j]
		}
	}
	if j == len(needle) {
		return i - len(needle)
	}
	return -1
}

這邊則是將需要搜尋的字串轉成前綴相似表，這也是整個KMP演算法最為核心的部分，不過因為需要一步步做推倒才能了解原理，雖然大致上與前段做搜尋比對的部分非常像，但如果想更加理解細節還是建議自行參考程式碼推完一次整個過程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func prefix(s string) []int {
	i := 1
	j := 0
	length := len(s)
	table := make([]int, length+1)
	for i < length {
		if s[i] == s[j] {
			i++
			j++
			table[i] = j
		} else if j == 0 {
			i++
		} else {
			j = table[j]
		}
	}
	return table
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func strStr(haystack string, needle string) int {
	var i int
	var j int
	table := prefix(needle)
	for i < len(haystack) && j < len(needle) {
		if haystack[i] == needle[j] {
			i++
			j++
		} else if j == 0 {
			i++
		} else {
			j = table[j]
		}
	}
	if j == len(needle) {
		return i - len(needle)
	}
	return -1
}
func prefix(s string) []int {
	i := 1
	j := 0
	length := len(s)
	table := make([]int, length+1)
	for i < length {
		if s[i] == s[j] {
			i++
			j++
			table[i] = j
		} else if j == 0 {
			i++
		} else {
			j = table[j]
		}
	}
	return table
}

總結:

要在一字串中找到目標字串的位置，最快的方式就是以KMP演算法來實作。

分享到