Trie 是一顆非典型的多叉樹模型。

前綴樹

struct TrieNode {
    bool isEnd; //該結(jié)點(diǎn)是否是一個(gè)串的結(jié)束
    TrieNode* next[26]; //字母映射表
};

TrieNode* next[26]中保存了對(duì)當(dāng)前結(jié)點(diǎn)而言下一個(gè)可能出現(xiàn)的所有字符的鏈接，因此我們可以通過(guò)一個(gè)父結(jié)點(diǎn)來(lái)預(yù)知它所有子結(jié)點(diǎn)的值：

for (int i = 0; i < 26; i++) {
    char ch = 'a' + i;
    if (parentNode->next[i] == NULL) {
        //說(shuō)明父結(jié)點(diǎn)的后一個(gè)字母不可為 ch
    } else {
       // 說(shuō)明父結(jié)點(diǎn)的后一個(gè)字母可以是 ch
    }
}

代碼實(shí)現(xiàn)：

class Trie {
private:
    bool isEnd;
    Trie* next[26];//定義類
public:
    Trie() {
        isEnd = false;
        memset(next, 0, sizeof(next));//初始化內(nèi)存方式，頭文件#include <string.h>
    }
    
 
   /*首先從根結(jié)點(diǎn)的子結(jié)點(diǎn)開始與 word 第一個(gè)字符進(jìn)行匹配，一直匹配到前綴鏈上沒(méi)有對(duì)應(yīng)的字符，
   這時(shí)開始不斷開辟新的結(jié)點(diǎn)，直到插入完 word 的最后一個(gè)字符，
   同時(shí)還要將最后一個(gè)結(jié)點(diǎn)isEnd = true;，表示它是一個(gè)單詞的末尾.*/
    void insert(string word) {
        Trie* node = this;
        for (char c : word) {
            if (node->next[c-'a'] == NULL) {
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->isEnd = true;
    }

    /*從根結(jié)點(diǎn)的子結(jié)點(diǎn)開始，一直向下匹配即可，如果出現(xiàn)結(jié)點(diǎn)值為空就返回false，如果匹配到了最后一個(gè)字符，那我們只需判斷node->isEnd即可。*/
    bool search(string word) {
        Trie* node = this;
        for (char c : word) {
            node = node->next[c - 'a'];
            if (node == NULL) {
                return false;
            }
        }
        return node->isEnd;
    }
    
    /*和 search 操作類似，只是不需要判斷最后一個(gè)字符結(jié)點(diǎn)的isEnd，因?yàn)榧热荒芷ヅ涞阶詈笠粋€(gè)字符，那后面一定有單詞是以它為前綴的。*/
    bool startsWith(string prefix) {
        Trie* node = this;
        for (char c : prefix) {
            node = node->next[c-'a'];
            if (node == NULL) {
                return false;
            }
        }
        return true;
    }
};

總結(jié)：

1. 形狀唯一。與插入順序和刪除順序無(wú)關(guān)。
2. 查找與Trie 中包含多少個(gè)單詞無(wú)關(guān)。都是單詞長(zhǎng)度L+1次。
3. 耗費(fèi)空間，如果 Trie 的高度為 n，字母表的大小為 m，最壞的情況是 Trie 中還不存在前綴相同的單詞，那空間復(fù)雜度就為 O(m^n)。
   一次建樹，多次查詢。

class WordDictionary {
public:
    bool isEnd;
    WordDictionary* next[26];
    /** Initialize your data structure here. */
    WordDictionary() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        WordDictionary* p = this;
        for(auto c : word) {
            if(p->next[c-'a'] == nullptr) 
                p->next[c-'a'] = new WordDictionary();
            p = p->next[c-'a'];
        }
        p->isEnd = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return searchWord(this, word);
    }
    bool searchWord(WordDictionary* node, string word) {
        if(word.size()==1) {  //邊界
            if(isalpha(word[0])) {
                if(node->next[word[0]-'a'] && node->next[word[0]-'a']->isEnd)
                    return true;
                return false;
            }
            else {
                for(int i=0; i<26; i++)
                    if(node->next[i] && node->next[i]->isEnd)
                        return true;
                return false;
            }
        }
        else {
            if(isalpha(word[0])) {
                if(node->next[word[0]-'a'])
                    return searchWord(node->next[word[0]-'a'], word.substr(1, word.size()-1));
                else
                    return false;
            }
            else {
                bool b;
                for(int i=0; i<26; i++) {      
                    if(node->next[i]){
                        b = searchWord(node->next[i], word.substr(1, word.size()-1));
                        if(b)   return true;
                    }
                }
                return false;
            }
        }
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

class TrieNode{
public:
    string word = "";
    vector<TrieNode*> nodes;
    TrieNode():nodes(26, 0){}
};

class Solution {
    int rows, cols;
    vector<string> res;
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        rows = board.size();
        cols = rows ? board[0].size():0;
        if(rows==0 || cols==0) return res;

        //建立字典樹的模板
        TrieNode* root = new TrieNode();
        for(string word:words){
            TrieNode *cur = root;
            for(int i=0; i<word.size(); ++i){
                int idx = word[i]-'a';
                if(cur->nodes[idx]==0) cur->nodes[idx] = new TrieNode();
                cur = cur->nodes[idx];
            }
            cur->word = word;
        }

        //DFS模板
        for(int i=0; i<rows; ++i){
            for(int j=0; j<cols; ++j){
                dfs(board, root, i, j);
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& board, TrieNode* root, int x, int y){
        char c = board[x][y];
        //遞歸邊界
        if(c=='.' || root->nodes[c-'a']==0) return;
        root = root->nodes[c-'a'];
        if(root->word!=""){
            res.push_back(root->word);
            root->word = "";
        }
        
        board[x][y] = '.';
        if(x>0) dfs(board, root, x-1, y);
        if(y>0) dfs(board, root, x, y-1);
        if(x+1<rows) dfs(board, root, x+1, y);
        if(y+1<cols) dfs(board, root, x, y+1);
        board[x][y] = c;
    }  
};