每日一道 LeetCode (9)：實現 strStr()

2020 年 8 月 7 日
筆記
leetcode

每天 3 分鐘，走上演算法的逆襲之路。

前文合集

每日一道 LeetCode 前文合集

程式碼倉庫

GitHub： //github.com/meteor1993/LeetCode

Gitee： //gitee.com/inwsy/LeetCode

題目：實現 strStr()

題目來源：//leetcode-cn.com/problems/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() 定義相符。

解題思路：暴力方案

解題思路？

這道題還搞啥解題思路？

題目都直接把答案寫出來了，「這與 C 語言的 strstr() 以及 Java的 indexOf() 定義相符」，我直接用 indexOf() 它不香么？

public int strStr(String haystack, String needle) {
    return haystack.indexOf(needle);
}

看著效率，杠杠的，我可真是個小機靈鬼。

但是如果你在面試的時候這麼答，會不會被面試打個半死我就不知道了。

那麼接下來，最符合常人的暴力思路來襲，我就喜歡干這事兒。

借一張官方的圖：

我做一個循環，直接比較 needle 長度的字元串，如果相等就可以直接返回了，如果比到最後沒比出來，就返回 -1 ，解題結束。

我就是這麼的直接。。。以及。。。暴力。。。

能用暴力解決的問題，絕不多動腦子。

public int strStr_1(String haystack, String needle) {

    int h = haystack.length(), n = needle.length();

    for (int i = 0; i < h - n + 1; i++) {
        if (needle.equals(haystack.substring(i, i + n))) {
            return i;
        }
    }

    return -1;
}

好像結果也還算可以嘛，沒有那種慢到不可接受。

解題思路：暴力方案優化

做完題好習慣看看答案，然後知道了我上面的這種暴力方案是基於一個叫「滑動窗口」的東西，這個名字倒是蠻形象的。

上面的暴力方案有一個缺點是，會將 haystack 所有長度為 n 的子串都和 needle 做比較，那麼能不能少比較幾次呢？

當然是可以的，以下內容來源於官網：

第一件事兒就是只有第一個字元相等的才有比較的意義，如果第一個字元都不相等，這也就不用比了（圖片來源於官方）。

接著一個字元一個字元比較，一旦不匹配了就立刻終止（圖片來源於官方）。

截止到目前，都還是很好理解的，下面這一步就稍微有點抽象了，而這個方案的精髓也是下面這一步。

這裡，比較到最後一位的時候發現不匹配，開始回溯。需要注意的是，pn 指針是移動到 pn = pn – curr_len + 1 的位置（圖片來源於官方）。

在這之後，接著 ++pn ，尋找開頭和 needle 第一位相同的子串，找到之後重複上面的比較的過程，然後找到了答案置（圖片來源於官方）。

實現程式碼如下（程式碼來自於官方）：

public int strStr_2(String haystack, String needle) {
    int L = needle.length(), n = haystack.length();
    if (L == 0) return 0;

    int pn = 0;
    while (pn < n - L + 1) {
        // 第一次循環 pn ，尋找和 needle 第一位相同的子串
        while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) ++pn;

        // 從 pn 開始，按位比較字元，獲得相同位數長度 currLen
        int currLen = 0, pL = 0;
        while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
            ++pn;
            ++pL;
            ++currLen;
        }

        // 如果 currLen 長度等於 needle 長度，匹配結束
        if (currLen == L) return pn - L;

        // 如果不等於，開始回溯
        pn = pn - currLen + 1;
    }
    return -1;
}

這段程式碼自己做了字元的循環比較，但是很不幸，這種比較方案要比使用 equals() 來的要慢，我稍微修改下：

public int strStr_3(String haystack, String needle) {
    int L = needle.length(), n = haystack.length();
    if (L == 0) return 0;
    int pn = 0;
    while (pn < n - L + 1) {
        // 第一次循環 pn ，尋找和 needle 第一位相同的子串
        while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0))  ++pn;
        // 如果 pn + L 的長度大於當前字元串長度，直接返回 -1
        if (pn + L > n) return -1;
        // 如果 pn + L 得到的子串和 needle 相同，直接返回 pn
        if (haystack.substring(pn, pn + L).equals(needle)) {
            return pn;
        }
        // 沒匹配到 ++pn
        ++pn;
    }
    return -1;
}

思路還是同樣的思路，但是我在字元串的比較換成了 equals() ，耗時重回 1ms 。

拋磚引玉

到這裡，我們往回看一個問題，為啥 jdk 提供的 indexOf() 這個方法，可以把耗時壓縮到 0ms ？為何 indexOf() 這個方法如此 NB ？

點開源碼，找到核心方法(jdk 版本: 1.8.0_221)：

static int indexOf(char[] source, int sourceOffset, int sourceCount,
        char[] target, int targetOffset, int targetCount,
        int fromIndex) {
    // 1、當開始查找位置 大於等於 源字元串長度時，如果[查找字元串]為空，則:
    // 返回字元串的長度，否則返回-1.
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    // 2、如果 fromIndex 小於 0 ，則從 0 開始查找。
    if (fromIndex < 0) {
        fromIndex = 0;
    }
    // 3、如果[查找字元串]為空，則返回 fromIndex
    if (targetCount == 0) {
        return fromIndex;
    }
    // 4、開始查找，從[查找字元串]中得到第一個字元，標記為 first
    char first = target[targetOffset];
    int max = sourceOffset + (sourceCount - targetCount);
    // 4.1、計算[源字元串最大長度]
    for (int i = sourceOffset + fromIndex; i <= max; i++) {
        // 4.2.1、從[源字元串]中，查找到第一個匹配到[目標字元串] first 的位置
        // for循環中，增加 while 循環
        /* Look for first character. */
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }
        // 4.2.2、如果在[源字元串]中，找到首個[目標字元串]，
        // 則匹配是否等於[目標字元串]
        /* Found first character, now look at the rest of v2 */
        if (i <= max) {
            // 4.2.2.1、得到下一個要匹配的位置，標記為 j
            int j = i + 1;
            // 4.2.2.2、得到其餘[目標字元串]的長度，標記為 end
            int end = j + targetCount - 1;
            // 4.2.2.3、遍歷，其餘[目標字元串]，從 k 開始，
            // 如果 j 不越界（小於 end ，表示：其餘[目標字元串]的範圍），
            // 同時[源字元串]==[目標字元串]，則
            // 自增，繼續查找匹配。 j++ 、 k++
            for (int k = targetOffset + 1; j < end && source[j]
                    == target[k]; j++, k++);
            // 4.2.2.4、如果 j 與 end 相等，則表示：
            // 源字元串中匹配到目標字元串，匹配結束，返回 i 。
            if (j == end) {
                /* Found whole string. */
                return i - sourceOffset;
            }
        }
    }
    return -1;
}

這段程式碼看起來平平無奇，而且查找的方式和我們上面的優化方案非常像，都是先查找首個匹配字元，然後再做循環查找整個匹配的字元串。

單純的靠程式碼優化把耗時從 2ms 縮減到了 0ms ，只能是一個大寫的佩服，不愧是寫 jdk 源碼的大神。

Tags: leetcode