208. Implement Trie (Prefix Tree)

這邊就是實作一個Trie

什麼是Trie, 他就是一種資料結構, 方便你把一整串的字變成一個樹圖

這樣做有什麼好處呢

假設你現在想要找 “apple”是否在[“app”, “abc”, “apple”]裡面, 一般來說我們能做的方式就是sequence的一個一個去找(O(MN)) N為要找的字串大小, 但用trie, 你可以將時間縮在O(N)

怎麼做呢, 我們先定義這個樹的節點, 這個節點有兩個值, 一個是這個節點是不是end, 另一個是這個節點會有一個dictionary, 可以去紀錄下一個字的節點指向誰

         node1
    (a) /    (b)\
      node2      node3
   (p)/   \ (b)
    node4 node5

以此類推, 就能建立一個存在很多個string的關係的樹

那查找就從root開始找, 找到後即可確認是不是最後一個node

c++的實作在這邊

class TrieNode{
    public:
        TrieNode():isEnd(false){};
        bool isEnd;
        unordered_map<char, TrieNode*> children;
};
class Trie {
public:
  
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode *node = root;
        for(auto w: word){
            if(!node->children.count(w)){
                node->children[w] = new TrieNode();
            }
            node = node->children[w];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode *node = root;
        for(auto w: word){
            if(!node->children.count(w)){
                return false;
            }
            node = node->children[w];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        TrieNode *node = root;
        for(auto w: prefix){
            if(!node->children.count(w)){
                return false;
            }
            node = node->children[w];
        }
        return true;
    }
      TrieNode *root{nullptr};
};
/**
 * 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);
 */