[Leetcode] Implement strStr() 實現StrStr

remcarpediem 發布于2019-08-14 12:26 / 2388人閱讀

摘要：最新更新暴力法復雜度時間空間思路本題有很多高級算法可以在時間內解決問題，然而這已經超出面試的范疇。本題在面試中出現的作用就是考察基本的編程素養，以及邊界條件的考慮。它使用一個數組，這個數組記錄了模式串自身的前綴和后綴的重復情況。

Implement strStr() 最新更新：https://yanjia.me/zh/2019/02/...

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

暴力法 復雜度

時間 O(N^2) 空間 O(1)

思路

本題有很多高級算法可以在O(N)時間內解決問題，然而這已經超出面試的范疇。本題在面試中出現的作用就是考察基本的編程素養，以及邊界條件的考慮。我們用暴力法即可。

代碼

public class Solution {
    public int strStr(String haystack, String needle) {
        int start = 0;
        // 如果剩下的字母不夠needle長度就停止遍歷
        while(start <= haystack.length() - needle.length()){
            int i1 = start, i2 = 0;
            while(i2 < needle.length() && haystack.charAt(i1)==needle.charAt(i2)){
                i1++;
                i2++;
            }
            if(i2 == needle.length()) return start;
            start++;
        }
        return -1;
    }
}

KMP算法 復雜度

時間 O(N+M) 空間 O(M)

思路

KMP算法是較為高級的算法。它使用一個next數組，這個數組記錄了模式串needle自身的前綴和后綴的重復情況。同樣是雙指針進行匹配，當失配時可以根據這個數組找到應該將模式串向后位移多少位，避免一些重復的比較。具體的解法這里有兩篇文章比較好，一篇是詳細講解KMP算法。

如果看完對產生next數組的方法還不太明白，還有一篇是講解next數組怎么得到的。

代碼

public class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0){
            return 0;
        }
        int[] next = new int[needle.length()];
        // 得到next數組
        getNextArr(next, needle);
        // i是匹配串haystack的指針，j是模式串needle的指針
        int i = 0, j = 0;
        // 雙指針開始匹配
        while(i < haystack.length() && j < needle.length()){
            // 如果j=-1意味著剛剛失配過，下標+1后，下一輪就可以開始匹配各自的第一個了
            // 如果指向的字母相同，則下一輪匹配各自的下一個
            if(j == -1 || haystack.charAt(i) == needle.charAt(j)){
                i++;
                j++;
            // 如果失配，則將更新j為next[j]
            } else {
                j = next[j];
            }
        }
        return j == needle.length() ? i - j : -1;
    }
    
    private void getNextArr(int[] next, String needle){
        // k是前綴中相同部分的末尾，同時也是相同部分的長度，因為長度等于k-0。
        // j是后綴的末尾，即后綴相同部分的末尾 
        int k = -1, j = 0;
        next[0] = -1;
        while(j < needle.length() - 1){
            // 如果k=-1，說明剛剛失配了，則重新開始計算前綴和后綴相同的長度
            // 如果兩個字符相等，則在上次前綴和后綴相同的長度加1就行了
            if (k == -1 || needle.charAt(j) == needle.charAt(k)){
                k++;
                j++;
                next[j] = k;
            } else {
            // 否則，前綴長度縮短為next[k]
                k = next[k];
            }
        }
    }
}

云服務器 GPU云服務器 strstr mb_strstr Implement LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64476.html

LeetCode 28：實現strStr() Implement strStr()

摘要：愛寫作者愛寫實現函數。說明當是空字符串時，我們應當返回什么值呢這是一個在面試中很好的問題。對于本題而言，當是空字符串時我們應當返回。這與語言的以及的定義相符。利用內建函數直接得結果。如果子字符串為空，返回。愛寫bug（ID：icodebugs）作者：愛寫bug 實現 strStr() 函數。給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符...

alaege 2019-08-16 18:31 評論0 收藏0
LeetCode 28：實現strStr() Implement strStr()

摘要：愛寫作者愛寫實現函數。說明當是空字符串時，我們應當返回什么值呢這是一個在面試中很好的問題。對于本題而言，當是空字符串時我們應當返回。這與語言的以及的定義相符。利用內建函數直接得結果。如果子字符串為空，返回。愛寫bug（ID：icodebugs）作者：愛寫bug 實現 strStr() 函數。給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符...

ivydom 2019-07-31 11:26 評論0 收藏0
leetcode 28 Implement strStr()

摘要：如果存在，返回子字符串的在長字符串的起始點的位置。如果不存在，則返回。就是遍歷長字符串，并通過比較字符找到是否存在目標子字符串。需要注意一下的就是對特殊情況的判斷，以減少無謂的時間消耗。題目詳情 Implement strStr().Return the index of the first occurrence of needle in haystack, or -1 if nee...

Gemini 2019-08-15 14:16 評論0 收藏0
[LeetCode] Implement strStr()

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 ...

fuyi501 2019-08-14 14:03 評論0 收藏0
leetcode28 Implement strStr() 在字符串中尋找目標字符串

摘要：題目要求在子字符串中尋找目標字符串，并返回該字符串第一次出現時的下標在嘗試的寫了一提中等難度的題目后，又一次回到簡單難度的題尋找溫暖思路一在原字符串中中尋找目標字符串首字母的下標，并提取子字符串，若該字符串的開頭等于目標字符串，則返回該下題目要求：在子字符串中尋找目標字符串，并返回該字符串第一次出現時的下標在嘗試的寫了一提中等難度的題目后，又一次回到簡單難度的題尋找溫暖T-T 思...

FingerLiu 2019-08-14 17:55 評論0 收藏0