###### tags: `LeetCode` `Medium` `Trie` `Object Oriented` `Tree`
# LeetCode #208 [Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/)
### (Medium)
Trie（發音類似 "try"）或者說 前綴樹 是一種樹形數據結構，用於高效地存儲和檢索字符串數據集中的鍵。這一數據結構有相當多的應用情景，例如自動補完和拼寫檢查。

請你實現 Trie 類：

Trie() 初始化前綴樹對象。
void insert(String word) 向前綴樹中插入字符串 word 。

boolean search(String word) 如果字符串 word 在前綴樹中，返回 true（即，在檢索之前已經插入）；否則，返回 false 。

boolean startsWith(String prefix) 如果之前已經插入的字符串 word 的前綴之一為 prefix ，返回 true ；否則，返回 false 。

---
目標為建構Trie類別。

首先先建構TrieNode類別, 該類別有兩個成員變數
1. bool is_word: 用於確認該節點為某個單字的結尾字元
2. vector<TrieNode*> children: 大小為26, 代表接在節點後的26個英文字母

再來做建構函式, 初始化is_word的值為false, 初始化宣告children。

再來做解構函式, 刪除所有子節點。

TrieNode有一個成員函式find, 輸入參數為const string&, 回傳型態為const TrieNode*, 函式內部不應該有任何修改。函式邏輯為, 讀入一個字元, 把它減去'a'的值作為索引找到children中的下一個節點, 如此反覆直到讀完全部的字元, 此時回傳指標。若途中指標為空指標, 代表指向的地方沒有被賦予值, 這代表之前沒有單字輸入, 所以找不到, 回傳空指標。

再來看到Trie類別:

Trie類別有一個成員變數: root_, 為unique_ptr, 在離開函數時會自動刪除, 因此Trie物件不需要寫解構元。

Tire物件的建構函式: 建立TrieNode類別的物件root_, 並呼叫TrieNode()建構函式進行初始化。

Trie物件的insert成員函式: 從root_節點開始, 讀入每一個word中的字元, 若節點不存在, 則建立節點再將指標指向節點; 若存在則直接更改指標指向節點, 最後在遍歷完整個word後, 將指標處的is_word改為true, 代表此節點為某個單字的終點。

Trie物件的search成員函式: 呼叫之前建立的TrieNode的find函式, find函式會回傳一個指標, 檢查指標是否為空指標, 以及指標的is_word是否為true, 若皆為true, 代表該單字存在。

Trie物件的startsWith成員函式: 與search類似, 但條件較為寬鬆, 輸入的字串不需要為單字(單字的節點的is_word為true), 只要確認開頭相等就好, 因此調用TrieNode的find函式, 並確認回傳指標是否為空指標即可。

---

class Trie {
public:

    unique_ptr<TrieNode> root_;
    Trie():root_(new TrieNode()){}
    
    void insert(const string& word) {
        TrieNode* p = root_.get();
        for(auto c:word){
            if(!p->children[c-'a'])//not exist
                p->children[c-'a'] = new TrieNode();
            p=p->children[c-'a'];
        }
        p->is_word = true;
    }
    
    bool search(const string& word) {
        const TrieNode* p = find(word);
        return p&&p->is_word;
    }
    
    bool startsWith(const string& prefix) {
        return find(prefix)!=nullptr;
    }
private:
    
    struct TrieNode{
        bool is_word;
        vector<TrieNode*> children;
        TrieNode():is_word(false), children(26, nullptr){}
        ~TrieNode(){
            for(auto c:children)
                if(c)delete c;
        }
    };
    
    const TrieNode* find(const string& word) const{
        TrieNode* p = root_.get();
        for(auto c:word){
            p=p->children[c-'a'];
            if(!p)return nullptr;
        }
        return p;
    }
};