緯緯道來
緯緯道來

研究所學生,主修資訊工程,熱衷於深度學習與機器學習。初期先以基本的程式教學為主,希望我的文章能夠幫助到你!(https://linktr.ee/johnnyhwu)

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

LeetCode logo

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”。

haystack 與 needle 範例

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

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

繼續檢查 needle 中下一個字元

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

繼續在 haystack 中找到可能為 needle 的字串
再次發現可能為 needle 之字串
繼續檢查 needle 中的其他字元
繼續檢查 needle 中的其他字元

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

Implement (Golang):

Supplementary:

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

未來,我也將會寫一篇文章來解釋這個演算法:)


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

CC BY-NC-ND 2.0

Like my work?
Don't forget to support or like, so I know you are with me..

Loading...
Loading...

Comment