本日文章主題是一個不難的資料結構 -- Trie 字典樹，它可以用來處理大量的字串，方便進行前綴詞查找 (prefix)，或者檢查某個字串是否存在於字典樹中。
以下Leetcode 題目中還很貼心地說 trie 與 "try" 發音相同。

Trie 的結構

• Trie 的根節點 (height=0) 不存儲任何值。
• Trie 中的非空節點高度等於它所代表的字串長度。
• Trie 的葉節點一定是一個完整的字串，但非葉節點可以是字串的前綴。
• 如果 Trie 節點儲存的是 "A" 到 "Z" 的字母，那麼每個節點的子節點則會代表該字母後續可能的字符。

圖片來自 Trie-維基

一個儲存了8個鍵的trie結構，"A", "to", "tea", "ted", "ten", "i", "in", "inn"

208. Implement Trie (Prefix Tree) (medium)

題目: 裸題，問 Trie 的函式怎麼做
Trie() 初始化 Trie 這 class
void insert(String word) 插入字串 word 到 trie
boolean search(String word) , 尋找字串 word 是否存在於 trie 中
boolean startsWith(String prefix) 檢查字串 prefix 是否存在於 trie 中

struct TrieNode {
    bool isWord = false;
    TrieNode *children [26]; 
};

class Trie {
public:
    TrieNode *root;
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode *ptr = root;
        for (char w: word) {
            if (!ptr->children[w-'a'])
                ptr->children[w-'a'] = new TrieNode();
            ptr = ptr->children[w-'a'];                     
        }
        ptr->isWord = true;
    }
    
    bool search(string word) {
        TrieNode *ptr = root;
        for (char w: word) {
            if (!ptr->children[w-'a'])
                return false;
            ptr = ptr->children[w-'a'];                     
        }
        return ptr->isWord;
    }
    
    bool startsWith(string prefix) {
        TrieNode *ptr = root;
        for (char w: prefix) {
            if (!ptr->children[w-'a'])
                return false;
            ptr = ptr->children[w-'a'];                     
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

未來要挑戰這題 139. Word Break，也是 trie 題，但難度變好高啊 0.0