摘要:愛寫作者愛寫實(shí)現(xiàn)函數(shù)。說明當(dāng)是空字符串時(shí),我們應(yīng)當(dāng)返回什么值呢這是一個(gè)在面試中很好的問題。對于本題而言,當(dāng)是空字符串時(shí)我們應(yīng)當(dāng)返回。這與語言的以及的定義相符。利用內(nèi)建函數(shù)直接得結(jié)果。如果子字符串為空,返回。
愛寫bug(ID:icodebugs)作者:愛寫bug
實(shí)現(xiàn) strStr() 函數(shù)。
給定一個(gè) haystack 字符串和一個(gè) needle 字符串,在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開始)。如果不存在,則返回 -1。
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba" Output: -1
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()).
說明:
當(dāng) needle 是空字符串時(shí),我們應(yīng)當(dāng)返回什么值呢?這是一個(gè)在面試中很好的問題。
對于本題而言,當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 。這與C語言的 strstr() 以及 Java的 indexOf()) 定義相符。
解題思路(Java):
? 復(fù)雜度:時(shí)間 O(n^2) 空間 O(1)
? 字符串 a 從第一個(gè)索引開始 逐一匹配字符串 b 的第一個(gè)索引:a[i++]==b[0],如果為true,則進(jìn)入內(nèi)循環(huán)字符串a(chǎn)從第 i+j 個(gè)字符開始與字符串b 第 j個(gè)字符匹配:a[i+j]==b[j]
class Solution { public int strStr(String haystack, String needle) { if(needle.equals(""))return 0; int haystackLen=haystack.length(),needleLen=needle.length(); char firstChar=needle.charAt(0); for(int i=0;i<=haystackLen-needleLen;i++){ if(haystack.charAt(i)==firstChar){ int j=1; for(;j
KMP算法:
? 復(fù)雜度:時(shí)間 O(n+m) 空間 O(M)
下面引用一組圖片幫助理解(圖片來源:https://blog.csdn.net/v_july_v/article/details/7041827 ):
? 說明: 圖片中字符串haystack為:"BBC ABCDAB ABCDABCDABDE",模式串 needle 為:"ABCDABD"
第一步開始匹配:第二步匹配到第一個(gè)相同字符:
第三步兩個(gè)字符串逐一向后匹配,直到到字符 D 與 空格 字符匹配失敗,結(jié)束該輪次匹配:
第四步重新匹配,但不用從第二步的下一個(gè)字符 B 開始,因?yàn)榭崭褡址芭c模式字符串前6個(gè)字符已經(jīng)匹配相同。既C字符之前的兩個(gè)字符 AB 與空格字符前兩個(gè)字符 AB 相同,兩個(gè)字符串可直接從 空白 字符與 C 字符開始匹配:
可以看到圖片中一下跳過了 haystack 五個(gè)字符ABCDAB 和 needle 的兩個(gè)字符AB。優(yōu)化思路很清晰。
代碼:
class Solution { public int strStr(String haystack, String needle) { if(needle.equals("")) return 0; int[] next = new int[needle.length()]; getNext(next, needle);// 得到next數(shù)組 // i是匹配串haystack的指針,j是模式串needle的指針 int i = 0, j = 0; while(i < haystack.length() && j < needle.length()){ // 如果j=-1,即next數(shù)組中該字符為第一位,下標(biāo)+1后,重新匹配 if(j == -1 || haystack.charAt(i) == needle.charAt(j)){ // 如果匹配成功,則自增1,匹配下一個(gè)字符 i++;j++; } else { j = next[j];// 如果匹配失敗,則將j賦值next[j],避免匹配重復(fù)匹配 } } return j == needle.length() ? i - j : -1; } private void getNext(int[] next, String needle){ // k是前綴中相同部分的末尾,也是相同部分的長度 // j是后綴的末尾,即后綴相同部分的末尾 int k = -1, j = 0; next[0] = -1; while(j < needle.length() - 1){ // 如果k=-1,匹配失敗,重新開始計(jì)算前綴和后綴相同的長度 // 如果兩個(gè)字符相等,則在上次前綴和后綴相同的長度加1,繼續(xù)下一段字符最大公共前后綴匹配 if (k == -1 || needle.charAt(j) == needle.charAt(k)){ k++;j++; if (needle.charAt(j) != needle.charAt(k)) next[j] = k; else //因?yàn)椴荒艹霈F(xiàn)p[j] = p[ next[j ]],所以當(dāng)出現(xiàn)時(shí)需要繼續(xù)遞歸,k = next[k] = next[next[k]],以減少重復(fù)部分的多余匹配 next[j] = next[k]; } else { // 否則,前綴長度縮短為next[k] k = next[k]; } } } }總結(jié):? KMP算法優(yōu)化的方向很明了,主要難點(diǎn)就在于對next數(shù)組的求法和理解,KMP算法不是本文的重點(diǎn),如有興趣深入了解,推薦一篇博文:https://blog.csdn.net/v_july_v/article/details/7041827
另外還有Sunday算法 是找到與模式字符串相同長度的源字符串 從右向左匹配,其中心思想為:
如果該字符沒有在模式串中出現(xiàn),直接從該字符向右移動(dòng)位數(shù) = 模式串長度 + 1。(因?yàn)樵醋址性撟址南嗤L度字符串不可能匹配)
如果該字符在模式串中出現(xiàn)過,其移動(dòng)位數(shù) = 模式串中最右端的該字符到末尾的距離+1。
字符串haystackBBC ABC 與模式串needle ABCDABD 匹配,字符串haystack中的空格字符未在模式串needle 中出現(xiàn),則可以直接跳過空格字符后面六個(gè)字符的匹配,因?yàn)榘崭褡址南嗤L度字符串都不可能匹配成功,所以可以跳過6個(gè)。
Python3:? 說明:上面兩種方法在所有語言都可行,只是語法不同,所以在py3中不再復(fù)現(xiàn),僅展示一些py3特有的語法投機(jī)取巧解題。
利用py3內(nèi)建函數(shù)find()直接得結(jié)果。
class Solution: def strStr(self, haystack: str, needle: str) -> int: return haystack.find(needle)find() 方法描述
find() 方法檢測字符串中是否包含子字符串 str ,如果指定 beg(開始) 和 end(結(jié)束) 范圍,則檢查是否包含在指定范圍內(nèi),如果指定范圍內(nèi)如果包含指定索引值,返回的是索引值在字符串中的起始位置。如果不包含索引值,返回-1。如果子字符串為空,返回0。
語法
str.find(str, beg=0, end=len(string))參數(shù)
str -- 指定檢索的字符串
beg -- 開始索引,默認(rèn)為0。
end -- 結(jié)束索引,默認(rèn)為字符串的長度。
利用py3字符出切片特性解決:
class Solution: def strStr(self, haystack: str, needle: str) -> int: for i in range(len(haystack)-len(needle)+1): if haystack[i:i+len(needle)]==needle:#截取切片 return i return -1注:算法導(dǎo)論第32章:字符串匹配有完整的一章相關(guān)討論。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/45112.html
摘要:愛寫作者愛寫實(shí)現(xiàn)函數(shù)。說明當(dāng)是空字符串時(shí),我們應(yīng)當(dāng)返回什么值呢這是一個(gè)在面試中很好的問題。對于本題而言,當(dāng)是空字符串時(shí)我們應(yīng)當(dāng)返回。這與語言的以及的定義相符。利用內(nèi)建函數(shù)直接得結(jié)果。如果子字符串為空,返回。 愛寫bug(ID:icodebugs)作者:愛寫bug 實(shí)現(xiàn) strStr() 函數(shù)。 給定一個(gè) haystack 字符串和一個(gè) needle 字符串,在 haystack 字符...
摘要:如果存在,返回子字符串的在長字符串的起始點(diǎn)的位置。如果不存在,則返回。就是遍歷長字符串,并通過比較字符找到是否存在目標(biāo)子字符串。需要注意一下的就是對特殊情況的判斷,以減少無謂的時(shí)間消耗。 題目詳情 Implement strStr().Return the index of the first occurrence of needle in haystack, or -1 if nee...
摘要:題目要求在子字符串中尋找目標(biāo)字符串,并返回該字符串第一次出現(xiàn)時(shí)的下標(biāo)在嘗試的寫了一提中等難度的題目后,又一次回到簡單難度的題尋找溫暖思路一在原字符串中中尋找目標(biāo)字符串首字母的下標(biāo),并提取子字符串,若該字符串的開頭等于目標(biāo)字符串,則返回該下 題目要求: 在子字符串中尋找目標(biāo)字符串,并返回該字符串第一次出現(xiàn)時(shí)的下標(biāo) 在嘗試的寫了一提中等難度的題目后,又一次回到簡單難度的題尋找溫暖T-T 思...
摘要:最新更新暴力法復(fù)雜度時(shí)間空間思路本題有很多高級算法可以在時(shí)間內(nèi)解決問題,然而這已經(jīng)超出面試的范疇。本題在面試中出現(xiàn)的作用就是考察基本的編程素養(yǎng),以及邊界條件的考慮。它使用一個(gè)數(shù)組,這個(gè)數(shù)組記錄了模式串自身的前綴和后綴的重復(fù)情況。 Implement strStr() 最新更新:https://yanjia.me/zh/2019/02/... Implement strStr().Re...
Problem Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Note 有substring,為何不用。 Solution public class Solution { public ...
閱讀 3233·2021-09-07 10:10
閱讀 3579·2019-08-30 15:44
閱讀 2578·2019-08-30 15:44
閱讀 2982·2019-08-29 15:11
閱讀 2219·2019-08-28 18:26
閱讀 2745·2019-08-26 12:21
閱讀 1113·2019-08-23 16:12
閱讀 3010·2019-08-23 14:57