算法面試真題詳解：字元串查找 II

描述

實作時間複雜度為 O(n + m)的方法 strStr。

strStr 傳回目标字元串在源字元串中第一次出現的第一個字元的位置. 目标字串的長度為 m , 源字串的長度為 n . 如果目标字串不在源字串中則傳回 -1。

線上評測位址：

領扣題庫官網

樣例1

輸入：source = "abcdef"， target = "bcd"

輸出：1

解釋：

字元串第一次出現的位置為1。

樣例2

輸入：source = "abcde"， target = "e"

輸出：4

字元串第一次出現的位置為4。

算法：HASH

• 字元串Hash可以通俗的了解為，把一個字元串轉換為一個整數。
• 如果我們通過某種方法，将字元串轉換為一個整數，就可以快速的判斷兩個字元串是否相同。

• 當然如果有不同的兩個字元串同時Hash到一個整數，這樣就比較麻煩了，是以我們希望構造這個Hash函數使得他們成為一個單射。

  算法思路

• 給定一個字元串S,對于一個字元c我們規定id(c)=c-'a'+1
• hash[i]=(hash[i-1]*p+id(s[i]))%MOD

• p和MOD均為質數，并且要盡量大

  代碼思路

  1. 計算target的hash值
  2. 計算source的hash值的過程中，依次計算每targetLen位的hash值。

     假設target長度為2，source為“abcd”

     hash("cd") = (hash("bc + d") - hash("b")*2 ) % BASE

     複雜度分析

     N表示字元串source長度，M表示字元串target長度

• 空間複雜度：O(1)
• 時間複雜度：O(N+M)

public class Solution {

private static final Integer BASE = 100007;

/*

 * @param source: A source string

 * @param target: A target string

 * @return: An integer as index

 */

public int strStr2(String source, String target) {

    if (source == null || target == null) {

        return -1;

    }

    int m = target.length();

    if (m == 0) {

        return 0;

    }

    int power = 1;

    for (int i = 0; i < m; i++) {

        power = (power * 31) % BASE;

    }

    //先計算一下target的hash值

    int targetCode = 0;

    for (int i = 0; i < m; i++) {

        targetCode = (targetCode * 31 + target.charAt(i)) % BASE;

    }

    //當source code 加上右邊一個character，就要減掉左邊的一個character

    int sourceCode = 0;

    for (int i = 0; i < source.length(); i++) {

        sourceCode = (sourceCode * 31 + source.charAt(i)) % BASE;

        if (i <= m - 1) {

            continue;

        }

        sourceCode = (sourceCode - power * source.charAt(i - m)) % BASE;

        if (sourceCode < 0) {

            sourceCode += BASE;

        }

        //若hash值相同，傳回答案

        if (sourceCode == targetCode) {

            return i - m + 1;

        }

    }

    return -1;

}           

}

更多題解參考：

九章官網solution