每日一道 LeetCode (9)：實現(xiàn) strStr()
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
每日一道 LeetCode 前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：實現(xiàn) strStr()
題目來源：https://leetcode-cn.com/problems/implement-strstr/
實現(xiàn) strStr()?函數(shù)。
給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)。如果不存在，則返回? -1。
示例 1:
輸入:?haystack?=?"hello",?needle?=?"ll"
輸出:?2
示例 2:
輸入:?haystack?=?"aaaaa",?needle?=?"bba"
輸出:?-1
說明:
當(dāng)?needle?是空字符串時，我們應(yīng)當(dāng)返回什么值呢？這是一個在面試中很好的問題。
對于本題而言，當(dāng)?needle?是空字符串時我們應(yīng)當(dāng)返回 0 。這與 C 語言的?strstr()?以及 Java的?indexOf()?定義相符。
解題思路：暴力方案
解題思路？
這道題還搞啥解題思路？
題目都直接把答案寫出來了，「這與 C 語言的?strstr()?以及 Java的?indexOf()?定義相符」，我直接用 indexOf() 它不香么？
public?int?strStr(String?haystack,?String?needle)?{
????return?haystack.indexOf(needle);
}
看著效率，杠杠的，我可真是個小機靈鬼。
但是如果你在面試的時候這么答，會不會被面試打個半死我就不知道了。
那么接下來，最符合常人的暴力思路來襲，我就喜歡干這事兒。
借一張官方的圖：
我做一個循環(huán)，直接比較 needle 長度的字符串，如果相等就可以直接返回了，如果比到最后沒比出來，就返回 -1 ，解題結(jié)束。
我就是這么的直接。。。以及。。。暴力。。。
能用暴力解決的問題，絕不多動腦子。
public?int?strStr_1(String?haystack,?String?needle)?{
????int?h?=?haystack.length(),?n?=?needle.length();
????for?(int?i?=?0;?i?1;?i++)?{
????????if?(needle.equals(haystack.substring(i,?i?+?n)))?{
????????????return?i;
????????}
????}
????return?-1;
}
好像結(jié)果也還算可以嘛，沒有那種慢到不可接受。
解題思路：暴力方案優(yōu)化
做完題好習(xí)慣看看答案，然后知道了我上面的這種暴力方案是基于一個叫 「滑動窗口」 的東西，這個名字倒是蠻形象的。
上面的暴力方案有一個缺點是，會將 haystack 所有長度為 n 的子串都和 needle 做比較，那么能不能少比較幾次呢？
當(dāng)然是可以的，以下內(nèi)容來源于官網(wǎng)：
第一件事兒就是只有第一個字符相等的才有比較的意義，如果第一個字符都不相等，這也就不用比了（圖片來源于官方）。
接著一個字符一個字符比較，一旦不匹配了就立刻終止（圖片來源于官方）。
截止到目前，都還是很好理解的，下面這一步就稍微有點抽象了，而這個方案的精髓也是下面這一步。
這里，比較到最后一位的時候發(fā)現(xiàn)不匹配，開始回溯。需要注意的是，pn 指針是移動到 pn = pn - curr_len + 1 的位置（圖片來源于官方）。
在這之后，接著 ++pn ，尋找開頭和 needle第一位相同的子串，找到之后重復(fù)上面的比較的過程，然后找到了答案置（圖片來源于官方）。
實現(xiàn)代碼如下（代碼來自于官方）：
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?1)?{
????????//?第一次循環(huán)?pn?，尋找和?needle?第一位相同的子串
????????while?(pn?1?&&?haystack.charAt(pn)?!=?needle.charAt(0))?++pn;
????????//?從?pn?開始，按位比較字符，獲得相同位數(shù)長度?currLen
????????int?currLen?=?0,?pL?=?0;
????????while?(pL?????????????++pn;
????????????++pL;
????????????++currLen;
????????}
????????//?如果?currLen?長度等于?needle?長度，匹配結(jié)束
????????if?(currLen?==?L)?return?pn?-?L;
????????//?如果不等于，開始回溯
????????pn?=?pn?-?currLen?+?1;
????}
????return?-1;
}
這段代碼自己做了字符的循環(huán)比較，但是很不幸，這種比較方案要比使用 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?1)?{
????????//?第一次循環(huán)?pn?，尋找和?needle?第一位相同的子串
????????while?(pn?1?&&?haystack.charAt(pn)?!=?needle.charAt(0))??++pn;
????????//?如果?pn?+?L?的長度大于當(dāng)前字符串長度，直接返回?-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、當(dāng)開始查找位置?大于等于?源字符串長度時，如果[查找字符串]為空，則:
????//?返回字符串的長度，否則返回-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、開始查找，從[查找字符串]中得到第一個字符，標(biāo)記為?first
????char?first?=?target[targetOffset];
????int?max?=?sourceOffset?+?(sourceCount?-?targetCount);
????//?4.1、計算[源字符串最大長度]
????for?(int?i?=?sourceOffset?+?fromIndex;?i?<=?max;?i++)?{
????????//?4.2.1、從[源字符串]中，查找到第一個匹配到[目標(biāo)字符串]?first?的位置
????????//?for循環(huán)中，增加?while?循環(huán)
????????/*?Look?for?first?character.?*/
????????if?(source[i]?!=?first)?{
????????????while?(++i?<=?max?&&?source[i]?!=?first);
????????}
????????//?4.2.2、如果在[源字符串]中，找到首個[目標(biāo)字符串]，
????????//?則匹配是否等于[目標(biāo)字符串]
????????/*?Found?first?character,?now?look?at?the?rest?of?v2?*/
????????if?(i?<=?max)?{
????????????//?4.2.2.1、得到下一個要匹配的位置，標(biāo)記為?j
????????????int?j?=?i?+?1;
????????????//?4.2.2.2、得到其余[目標(biāo)字符串]的長度，標(biāo)記為?end
????????????int?end?=?j?+?targetCount?-?1;
????????????//?4.2.2.3、遍歷，其余[目標(biāo)字符串]，從?k?開始，
????????????//?如果 j 不越界（小于 end ，表示：其余[目標(biāo)字符串]的范圍），
????????????//?同時[源字符串]==[目標(biāo)字符串]，則
????????????//?自增，繼續(xù)查找匹配。j++?、 k++
????????????for?(int?k?=?targetOffset?+?1;?j?????????????????????==?target[k];?j++,?k++);
????????????// 4.2.2.4、如果 j 與 end 相等，則表示：
????????????//?源字符串中匹配到目標(biāo)字符串，匹配結(jié)束，返回 i 。
????????????if?(j?==?end)?{
????????????????/*?Found?whole?string.?*/
????????????????return?i?-?sourceOffset;
????????????}
????????}
????}
????return?-1;
}
這段代碼看起來平平無奇，而且查找的方式和我們上面的優(yōu)化方案非常像，都是先查找首個匹配字符，然后再做循環(huán)查找整個匹配的字符串。
單純的靠代碼優(yōu)化把耗時從 2ms 縮減到了 0ms ，只能是一個大寫的佩服，不愧是寫 jdk 源碼的大神。
