實現 strStr（Implement-StrStr）

題幹如下：

實現 strStr() 函數。

給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從0開始)。如果不存在，則返回  -1。

示例 1:

輸入: haystack = "hello", needle = "ll"

輸出: 2

示例 2:

輸入: haystack = "aaaaa", needle = "bba"

輸出: -1

說明:

當 needle 是空字符串時，我們應當返回什麼值呢？這是一個在面試中很好的問題。

對於本題而言，當 needle 是空字符串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

來源：力扣

本題有很多種解題方式，爲了再鞏固一下 雙指針解題思路 這題我們還是選用這種思路來解。

建議再結合 讓我們一起啃算法----移除元素 和 讓我們一起啃算法----刪除排序數組中的重複項 兩篇文章仔細體會一下 雙指針思路 。

解題思路

初始化 i 指向 needle 字符串的第一個字符， j 指向 haystack 字符串的第一個字符。比較 needle[i] 與 haystack[j] 的字符是否相等：相等則 i++、j++ ；不想等則 i 重新指向 needle 字符串的第一個字符， j 指向上一次初始位置的後一個字符。

注： j 指向上一次初始位置的後一個字符的計算方式爲： j = j - i + 1。可以自己造個數組，推算一下這個規律喲。

流程圖如下：

代碼實現

GO語言實現

func strStr(haystack string, needle string) int {

    // 子串爲空則返回 0
    if needle == "" {
        return 0
    }

    i := 0
    j := 0
    for j < len(haystack) {
        // 判斷 haystack[j] 與 needle[i] 是否相等，不想等，則 i 重新指向 needle 字符串的首字符，即 i = 0
        // j 指向 j上一次初始化的後一個字符串，即 j = j - i + 1
        if haystack[j] != needle[i] {
            j = j - i + 1
            i = 0
        } else {
            // haystack[j] 與 needle[i] 相等，則先判斷 i 是否已經最大
            // 是的話就返回 needle 在 haystack 的第一個位置，計算方式： j - i
            if i == len(needle) -1 {
                return j - i
            }
            // 如果 i 不是 needle 的最大索引，那麼 j 向後移動一位，i 向後移動一位，繼續比較
            j++
            i++
        }
    }
    // j 越界了，說明不存在子串 needle，即返回 -1
    return -1
}

總結

相關文章