[Leetcode] Implement strStr() 實(shí)現(xiàn)StrStr

remcarpediem 發(fā)布于2019-08-14 12:26 / 2394人閱讀

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

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.

暴力法 復(fù)雜度

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

思路

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

代碼

public class Solution {
    public int strStr(String haystack, String needle) {
        int start = 0;
        // 如果剩下的字母不夠needle長(zhǎng)度就停止遍歷
        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算法 復(fù)雜度

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

思路

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

如果看完對(duì)產(chǎn)生next數(shù)組的方法還不太明白，還有一篇是講解next數(shù)組怎么得到的。

代碼

public class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0){
            return 0;
        }
        int[] next = new int[needle.length()];
        // 得到next數(shù)組
        getNextArr(next, needle);
        // i是匹配串haystack的指針，j是模式串needle的指針
        int i = 0, j = 0;
        // 雙指針開(kāi)始匹配
        while(i < haystack.length() && j < needle.length()){
            // 如果j=-1意味著剛剛失配過(guò)，下標(biāo)+1后，下一輪就可以開(kāi)始匹配各自的第一個(gè)了
            // 如果指向的字母相同，則下一輪匹配各自的下一個(gè)
            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是前綴中相同部分的末尾，同時(shí)也是相同部分的長(zhǎng)度，因?yàn)殚L(zhǎng)度等于k-0。
        // j是后綴的末尾，即后綴相同部分的末尾 
        int k = -1, j = 0;
        next[0] = -1;
        while(j < needle.length() - 1){
            // 如果k=-1，說(shuō)明剛剛失配了，則重新開(kāi)始計(jì)算前綴和后綴相同的長(zhǎng)度
            // 如果兩個(gè)字符相等，則在上次前綴和后綴相同的長(zhǎng)度加1就行了
            if (k == -1 || needle.charAt(j) == needle.charAt(k)){
                k++;
                j++;
                next[j] = k;
            } else {
            // 否則，前綴長(zhǎng)度縮短為next[k]
                k = next[k];
            }
        }
    }
}