208. Implement Trie (Prefix Tree)

題目網址：https://leetcode.cn/problems/implement-trie-prefix-tree/

題意：Trie 也稱作 prefix tree, 是一種可以高效儲存、取得 string 中的 key 的資料結構。這一資料結構有相當多的應用情境, 例如 : 自動補全和拼寫檢查。

請實現 Trie class：

• Trie()：初始化 trie object
• void insert(String word)：插入 word
• bool search(String word)：返回 word 是否已經存在於 trie 中
• boolean startsWith(String prefix) ：若已經插入的 word 的前綴之一為 prefix, 則 return true

注意：word 和 prefix 僅由小寫字母所組成。

Solution：

想法：先用一個 root 作為所有開頭 TrieNode 之 dummy node

• Trie() : 初始化 root
• void insert(String word) : 遍歷 word 中的每個 char, 若 p->children[ch - 'a'] 為 null, 則新增一 TrieNode 並指向它, 當走到 word 之 end, 記得將 trie 中的 end node 之 isEnd 設為 true
• bool search(String word) 和 boolean startsWith(String prefix) : 兩者皆得遍歷傳入參數的每個 char, 因此我額外寫了一個 TrieNode* find(string& word) 來遍歷
  • TrieNode* find(string& word) : 若 word 不在 trie 中, 則返回 nullptr。否則, 返回 end node 之 ptr
  • bool search(String word) : 若 end node 之 ptr p 存在, 且 p->isEnd 為 true
    ➔ 代表 word 存在 trie 中, 因此返回 true
  • boolean startsWith(String prefix) : 若 end node 之 ptr p 存在
    ➔ 代表 prefix 存在 trie 中, 因此返回 true

e.g. 下圖為插入 ["app", "ape", "at", "atp", "to"] 後的 trie, 每個 TrieNode 中的是 char 和 is_end

class TrieNode {
public:
    TrieNode* children[26] = {nullptr};
    bool isEnd = false; // 預設每個 char 不為 end
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode *cur = root;
        for (auto& ch : word) {
            const int i = ch - 'a';
            if (!cur->children[i]) {
                cur->children[i] = new TrieNode();
            }
            cur = cur->children[i];
        }
        cur->isEnd = true; // 將最後一個 char 設為 end
    }

    bool search(string word) {
        // 不僅 word 要在 trie 中, 且 word 的最後一個 char 還必須是 end
        TrieNode *p = find(word);
        return (p != nullptr) && p->isEnd;
    }

    bool startsWith(string prefix) {
        // 代表 prefix 為 trie 的前綴之一
        return find(prefix) != nullptr;
    }

private:
    TrieNode *root;

    // 若 word 不在 trie 中, 則返回 nullptr; 否則, 返回 end node 之 ptr
    TrieNode* find(string& word){
        TrieNode *p = root;
        for (const auto& ch : word) {
            const int i = ch - 'a';

            if (!p->children[i]) {
                return nullptr;
            }

            p = p->children[i];
        }
        return p;
    }
};

• time：
  • $O(1)$ ➔ 初始化 Trie
  • $O(n)$ ➔ insert、search 和 startWith, n 為要查詢或插入的 string 長度
• space：$O(26 \cdot \displaystyle\sum_{i=1}^{n}w_i)$ ➔ worse case：每個 word 的 prefix 皆不重覆
  • $\displaystyle\sum_{i=1}^{n}w_i$：所有要插入的 string 長度之和（最大 node 數）
  • $O(26)$ : 每個 node 有 26 個 children