[LeetCode] 208. Implement Trie (Prefix Tree) 實(shí)現(xiàn)字典樹(前綴樹)

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");  
trie.search("app");     // returns true

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

這道題讓我們實(shí)現(xiàn)一個(gè)重要但又有些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)-字典樹， 又稱前綴樹或單詞查找樹，例如，一個(gè)保存了8個(gè)鍵的trie結(jié)構(gòu)，"A", "to", "tea", "ted", "ten", "i", "in", and "inn"。

字典樹主要有如下三點(diǎn)性質(zhì)：

1. 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)意外每個(gè)節(jié)點(diǎn)只包含一個(gè)字符。

2. 從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。

3. 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符串不相同。

字母樹的插入（Insert）、刪除（ Delete）和查找（Find）都非常簡單，用一個(gè)一重循環(huán)即可，即第i 次循環(huán)找到前i 個(gè)字母所對(duì)應(yīng)的子樹，然后進(jìn)行相應(yīng)的操作。實(shí)現(xiàn)這棵字母樹，我們用最常見的數(shù)組保存（靜態(tài)開辟內(nèi)存）即可，當(dāng)然也可以開動(dòng)態(tài)的指針類型（動(dòng)態(tài)開辟內(nèi)存）。至于結(jié)點(diǎn)對(duì)兒子的指向，一般有三種方法：

1、對(duì)每個(gè)結(jié)點(diǎn)開一個(gè)字母集大小的數(shù)組，對(duì)應(yīng)的下標(biāo)是兒子所表示的字母，內(nèi)容則是這個(gè)兒子對(duì)應(yīng)在大數(shù)組上的位置，即標(biāo)號(hào)；

2、對(duì)每個(gè)結(jié)點(diǎn)掛一個(gè)鏈表，按一定順序記錄每個(gè)兒子是誰；

3、使用左兒子右兄弟表示法記錄這棵樹。

三種方法，各有特點(diǎn)。第一種易實(shí)現(xiàn)，但實(shí)際的空間要求較大；第二種，較易實(shí)現(xiàn)，空間要求相對(duì)較小，但比較費(fèi)時(shí)；第三種，空間要求最小，但相對(duì)費(fèi)時(shí)且不易寫。 

我們這里只來實(shí)現(xiàn)第一種方法，這種方法實(shí)現(xiàn)起來簡單直觀，字母的字典樹每個(gè)節(jié)點(diǎn)要定義一個(gè)大小為 26 的子節(jié)點(diǎn)指針數(shù)組，然后用一個(gè)標(biāo)志符用來記錄到當(dāng)前位置為止是否為一個(gè)詞，初始化的時(shí)候講 26 個(gè)子節(jié)點(diǎn)都賦為空。那么 insert 操作只需要對(duì)于要插入的字符串的每一個(gè)字符算出其的位置，然后找是否存在這個(gè)子節(jié)點(diǎn)，若不存在則新建一個(gè)，然后再查找下一個(gè)。查找詞和找前綴操作跟 insert 操作都很類似，不同點(diǎn)在于若不存在子節(jié)點(diǎn)，則返回 false。查找次最后還要看標(biāo)識(shí)位，而找前綴直接返回 true 即可。代碼如下：

class TrieNode {
public:
    TrieNode *child[26];
    bool isWord;
    TrieNode(): isWord(false) {
        for (auto &a : child) a = nullptr;
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    void insert(string s) {
        TrieNode *p = root;
        for (auto &a : s) {
            int i = a - 'a';
            if (!p->child[i]) p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }
    bool search(string key) {
        TrieNode *p = root;
        for (auto &a : key) {
            int i = a - 'a';
            if (!p->child[i]) return false;
            p = p->child[i];
        }
        return p->isWord;
    }
    bool startsWith(string prefix) {
        TrieNode *p = root;
        for (auto &a : prefix) {
            int i = a - 'a';
            if (!p->child[i]) return false;
            p = p->child[i];
        }
        return true;
    }
    
private:
    TrieNode* root;
};

Github 同步地址： 

https://github.com/grandyang/leetcode/issues/208

類似題目：

Add and Search Word - Data structure design

Design Search Autocomplete System

Replace Words

Implement Magic Dictionary

參考資料：

https://leetcode.com/problems/implement-trie-prefix-tree/

https://leetcode.com/problems/implement-trie-prefix-tree/discuss/58832/AC-JAVA-solution-simple-using-single-array

https://leetcode.com/problems/implement-trie-prefix-tree/discuss/58986/Concise-O(1)-JAVA-solution-based-on-HashMap

https://leetcode.com/problems/implement-trie-prefix-tree/discuss/58842/Maybe-the-code-is-not-too-much-by-using-%22next26%22-C%2B%2B

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(208.實(shí)現(xiàn)字典樹(前綴樹))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)實(shí)現(xiàn)字典樹(前綴樹)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！