【面試高頻題】難度 2.5/5，簡單結合 DFS 的 Trie 模闆級運用題

題目描述

這是 LeetCode 上的 677. 鍵值映射 ，難度為 中等。

Tag : 「字典樹」、「DFS」、「哈希表」

實作一個 ​

​MapSum​

​​ 類，支援兩個方法，​

​insert​

​​ 和 ​

​sum​

​：

• ​

  ​MapSum()​

  ​​ 初始化​

  ​MapSum​

  ​ 對象
• ​

  ​void insert(String key, int val)​

  ​​ 插入​

  ​key-val​

  ​​ 鍵值對，字元串表示鍵​

  ​key​

  ​​ ，整數表示值​

  ​val​

  ​​ 。如果鍵​

  ​key​

  ​ 已經存在，那麼原來的鍵值對将被替代成新的鍵值對。
• ​

  ​int sum(string prefix)​

  ​​ 傳回所有以該字首​

  ​prefix​

  ​​ 開頭的鍵​

  ​key​

  ​ 的值的總和。

示例：

輸入：
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

輸出：
[null, null, 3, null, 5]

解釋：
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)      

提示：

• ​

  ​key​

  ​​ 和​

  ​prefix​

  ​ 僅由小寫英文字母組成
• ​

  ​1 <= val <= 1000​

  ​
• 最多調用​

  ​50​

  ​​ 次​

  ​insert​

  ​​ 和​

  ​sum​

  ​

Trie + DFS

從需要實作「存儲字元串（映射關系）」并「檢索某個字元串字首的總和」來看，可以知道這是與 相關的題目，還不了解 的同學可以先看前置 🧀：​實作 Trie (字首樹) 。

考慮如何實作兩個操作：

• ​

  ​insert​

  ​​ ：在基本的 插入操作的基礎上進行拓展即可。與正常的插入操作的唯一差別為，不能簡單記錄單詞的結束位置，還要存儲 對應的 是多少。具體的我們可以使用 ​

  ​int​

  ​ 類型的數組 來代替原有的 ​

  ​boolean​

  ​ 類型的數組 ；
• ​

  ​sum​

  ​​ ： 先對入參 進行字典樹搜尋，到達尾部後再使用 ​

  ​DFS​

  ​ 搜尋後面的所有方案，并累加結果。

代碼（​

​static​

​​ 優化代碼見 ，避免每個樣例都 ​​

​new​

​ 大數組）：

class MapSum{
    int[][] tr = new int[2510][26];
    int[] hash = new int[2510];
    int idx;
    public void insert(String key, int{
        int p = 0;
        for (int i = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        hash[p] = val;
    }
    public int sum(String prefix){
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return dfs(p);
    }
    int dfs(int{
        int ans = hash[p];
        for (int u = 0; u < 26; u++) {
            if (tr[p][u] != 0) ans += dfs(tr[p][u]);
        }
        return      

class MapSum{
    static int[][] tr = new int[2510][26];
    static int[] hash = new int[2510];
    static int idx;
    public MapSum(){
        for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0);
        Arrays.fill(hash, 0);
        idx = 0;
    }
    public void insert(String key, int{
        int p = 0;
        for (int i = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        hash[p] = val;
    }
    public int sum(String prefix){
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return dfs(p);
    }
    int dfs(int{
        int ans = hash[p];
        for (int u = 0; u < 26; u++) {
            if (tr[p][u] != 0) ans += dfs(tr[p][u]);
        }
        return      

• 時間複雜度：令的最大長度為，最大調用次數為，字元集大小為（ 本題固定為），​​

  ​insert​

  ​​ 操作的複雜度為；從​​

  ​DFS​

  ​​ 的角度分析，​

  ​sum​

  ​​ 操作的複雜度為，但事實上，對于本題具有明确的計算量上界，搜尋所有的格子的複雜度為
• 空間複雜度：

Trie 記錄字首字元串總和

為降低 ​

​sum​

​​ 操作的複雜度，我們可以在 ​

​insert​

​ 操作中同時記錄（累加）每個字首的總和。

代碼（​

​static​

​​ 優化代碼見 ，避免每個樣例都 ​​

​new​

​ 大數組）：

class MapSum{
    int N = 2510;
    int[][] tr = new int[N][26];
    int[] hash = new int[N];
    int idx;
    Map<String, Integer> map = new HashMap<>();
    public void insert(String key, int{
        int _val = val;
        if (map.containsKey(key)) val -= map.get(key);
        map.put(key, _val);
        for (int i = 0, p = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
            hash[p] += val;
        }
    }
    public int sum(String prefix){
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return      

class MapSum{
    static int N = 2510;
    static int[][] tr = new int[N][26];
    static int[] hash = new int[N];
    static int idx;
    static Map<String, Integer> map = new HashMap<>();
    public MapSum(){
        for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0);
        Arrays.fill(hash, 0);
        idx = 0;
        map.clear();
    }
    public void insert(String key, int{
        int _val = val;
        if (map.containsKey(key)) val -= map.get(key);
        map.put(key, _val);
        for (int i = 0, p = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
            hash[p] += val;
        }
    }
    public int sum(String prefix){
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return      

• 時間複雜度：令的最大長度為，​​

  ​insert​

  ​​ 操作的複雜度為；​​

  ​sum​

  ​​ 操作的複雜度為
• 空間複雜度：令的最大長度為，最大調用次數為，字元集大小為（ 本題固定為），複雜度為

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.677​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。