LeetCode’s Note: (28) Implement strStr()

Question:

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 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Example 3:

Input: haystack = "", needle = ""
Output: 0

Explanation:

這題的題意相當的清晰，就是要從字串（haystack）中找到指定的字串（needle），並回傳 needle 在 haystack 中第一次出現的 index。如果 needle 的長度為零時，則直接回傳 0；如果在 haystack 中找不到 needle 的話，就回傳 -1。

Brute Force:

看完題目之後，腦中浮現了第一個想法：依序檢查 haystack 中的每一個字元，如果對上了 needle 中的第一個字元後，則表示可能找到了 needle。所以，就可以透過第二個迴圈繼續檢查 needle 中剩下的字元。

接下來，我們透過一個簡單例子來說明 Brute Force 的概念。如下圖所示，haystack = “YYXQAPPHMD”，needle = “APP”。

以 Brute Force 的方法，我們會依序檢查 haystack 中的每一個字元，直到檢查到的字元與 needle 中的第一個字元相同為止。

當檢查到與 needle 中的第一個字元相同時，就可以透過第二個迴圈（j）來繼續檢查後面的字元是否與 needle 中的相同。要使用第二個迴圈（j）而不繼續使用原來的檢查是因為我們必須保留 i 的位置。因為如果繼續檢查剩下的字元時發現不正確時，我們才能再從 i 繼續找到可能出現的 needle。

如上圖所示，繼續檢查 needle 中剩下的字元時，發現 B 與 P 並不相同，所以我們必須繼續在 haystack 中，繼續找到可能為 needle 的字串。

如上圖所示，最後我們在 haystack 中找到了 needle，則回傳 i 。

Implement (Golang):

Supplementary:

雖然透過 Brute Force 就可以解決這個問題，但是「字串尋找」的問題在電腦科學中是被歸類為 Pattern Searching 的問題。著名的 Knuth–Morris–Pratt algorithm（簡稱 KMP 演算法），就是能夠有效率的解決這個問題。

未來，我也將會寫一篇文章來解釋這個演算法：）

希望本篇文章解釋得夠詳盡與簡單，能夠給予在學習程式的你實質的幫助，也可以在底下幫我拍拍手 😆 或是支持我 😇。