快速判斷兩個字元串是否相等：字元串哈希

LeetCode 2430. 對字母串可執行的最大删除數

給你一個僅由小寫英文字母組成的字元串 s 。在一步操作中，你可以：

• 删除 整個字元串 s ，或者
• 對于滿足 1 < = i < = s . l e n g t h / 2 1 <= i <= s.length / 2 1<=i<=s.length/2 的任意 i ，如果 s 中的 前 i 個字母和接下來的 i 個字母 相等 ，删除 前 i 個字母。

例如，如果 s = “ababc” ，那麼在一步操作中，你可以删除 s 的前兩個字母得到 “abc” ，因為 s 的前兩個字母和接下來的兩個字母都等于 “ab” 。

傳回删除 s 所需的最大操作數。

提示：

• 1 < = s . l e n g t h < = 4000 1 <= s.length <= 4000 1<=s.length<=4000
• s 僅由小寫英文字母組成

思路

首先一個字元串至少可以通過一次操作使其變成空串。那麼如果需要最大化操作次數，就需要盡可能多的使用操作2。如果目前字元串s的某個字首s[1,i]=s[i+1,2*i]相同的話，那麼可以通過操作2來删除前i個字元。可以對于字元串s，可能存在多種方案使其删除某個字首，但是對于每種方案都可能對後續産生不同的影響，是以此時使用記憶化搜尋來求解。但對于每一次記憶化搜尋，都需要在 O ( 1 ) O(1) O(1)的時間複雜度下快速判斷某個字首子字元串與後續的子字元串是否相等，此時可以使用字元串哈希來快速判斷。字元串哈希就是将字元串當作一個P進制數，然後将其轉化為10進制數來計算某個字首的哈希值。計算某個子字元串s[i,j]的哈希值時，可通過 f [ j ] − f [ i − 1 ] ∗ P j − i + 1 f[j]-f[i-1]*P^{j-i+1} f[j]−f[i−1]∗Pj−i+1來快速計算，進而快速實作字元串的比較。

代碼

class Solution {

    long[] f, p;
    int P = 131;
    int n;
    int[] ff;

    public int deleteString(String s) {
        n = s.length();
        f = new long[n+1];
        p = new long[n+1];
        ff = new int[n];
        init(s);
        return dfs(s,0);
    }

    public void init(String s) {
        p[0] = 1;
        for(int i = 1; i <= n; i++) {
            f[i] = f[i-1] * P + s.charAt(i-1);
            p[i] = p[i-1] * P;
        }
    }

    public int dfs(String s, int u) {
        if(u == n) {
            return 0;
        }
        if(ff[u] != 0) {
            return ff[u];
        }
        int len = n - u;
        ff[u] = 1;
        for(int i = 1; i <= len / 2; i++) {
            if(get(u+1,u+i) == get(u+i+1,u+2*i)) {
                ff[u] = Math.max(ff[u], dfs(s,u+i) + 1);
            }
        }
        return ff[u];
    }

    public long get(int a, int b) {
        return f[b] - f[a-1] * p[b-a+1];
    }
}