28. Implement strStr()

Level : Easy

原題連結 : Click

題目 :

Implement strStr().

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

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

Example :

解題思路 :

• 這題其實如果要得到線性的時間複雜度的話需要使用KMP Algorithm，並沒有很簡單
• KMP主要在尋找子字串時使用，他的核心概念就是他會需要生成一個next table

何謂next table呢? 假設一個情境當你有一個字串ABBCABBCDEABBCF，需要你找出ABBCF字串的位置，當你從頭一個一個比對時，會在第5個字符出現不一樣，A 與 F 這時候就要去next table的第五個也就是index = 4 的位置看從哪裡開始重新比對才有效率，這時候next table會再index = 4的的值會是 0，也就是再跟你說你需要從index = 0的地方重新尋找，這時候你需要重新回到ABBCF的開頭A去比對ABBCABBCDEABBCF中的第5格字符A，然後以次類推繼續尋找，當只要碰壁就去請教next table，你該從哪裡重新開始檢查。

• 那第二個重點就是如何製作next table ?

其實只需要用two pointers就可以找到next table，這邊要提醒一下，next table的寫法有很多種，我這邊只展示將當前element 的 next value都填在上一個element的位置，也就是說假設一個子字串ABCABF的next table會像是000120，當F碰壁時，就會去找到F的上一個value也就是2，也就是說他會告訴你該去index = 2 的地方也就是C重新開始檢查，以此類推…

以下是我的解法 - time complexity: O(n+m) , space complexity: O(n)

為何能做到O(n+m)呢? 因為他只是在主程式部分時將主字串traversal一遍與製作next table時將子字串traversal一遍 Runtime: 0 ms, faster than 100.00% of Go online submissions for Implement strStr().

 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
39
40
41
42
43
44
45
46
47

func strStr(haystack string, needle string) int {
    
    n := len(needle)
    if n == 0 {
        return 0 
    }
    
    next := make([]int, len(needle))
    getNext(next, needle)
    
    j := 0
    for i := 0; i < len(haystack); i++ {
        for j > 0 && haystack[i] != needle[j] {
            j = next[j-1]
        }
        
        if haystack[i] == needle[j] {
            j++
        }
        if j == n {
            return i - n + 1
        }
        
    }
    return -1
    
    
}

func getNext(next []int, s string) {
    j := 0
    for i := 1; i < len(s); i++ {
        for j > 0 && s[i] != s[j] {
            j = next[j-1]
        }
        
        if s[i] == s[j] {
            j++
        }   
    
        next[i] = j
    }
    

}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!