208. Implement Trie (Prefix Tree)

這是系統設計題, 我們先要了解他的題意

他想要我們能create出一個Trie,

我們可以先去定義Trie的Node

然後分別為insert, search, startwith

insert的話就是從root一路往下走, 若是缺乏的我們就create, 順便在最後一個節點紀錄到這邊是一個完整的string

search 就是走完所有的節點, 一旦遇到為空的就代表有缺, 直接回傳false,若能走完, 還要再檢查一下他是否有被記錄成string

startwith就跟search一樣, 但他不用檢查string紀錄, 更簡單

class TrieNode {
public:
    // ininit datat structure 
    bool is_word;
    TrieNode *children[26];
    TrieNode (){
        is_word = false;
        for(int i = 0; i < 26;i++){
            children[i] = nullptr;
        }
    }
};
class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        int wordLen = word.size();
        TrieNode *cur = root;
        for(int i = 0; i < wordLen;i++){
            int c = word[i] - 'a';
            if(!cur->children[c]){
                cur->children[c] = new TrieNode();
            }
            cur = cur->children[c];
        }
        cur->is_word = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        int wordLen = word.size();
        TrieNode *cur = root;
        for(int i = 0; i < wordLen; i++){
            int c = word[i] - 'a';
            if(!cur->children[c]) return false;
            cur = cur->children[c];
        }
        return cur->is_word;
}
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        int wordLen = prefix.size();
        TrieNode *cur = root;
        for(int i = 0; i < wordLen; i++){
            int c = prefix[i] - 'a';
            if(!cur->children[c]) return false;
            cur = cur->children[c];
        }
        return true;
    }
    TrieNode *root;
};
/**
 * 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);
 */