iT邦幫忙

1

資結經典題目: 實作一個Trie (又稱prefix tree、字典樹、前綴樹)

今天在練習leetcode時,
看到這樣一個題目: LeetCode- 208. Implement Trie (Prefix Tree)

是一個沒看過的資料結構,查了很多資料之後,
終於大概知道這個資料結構- trie是做什麼用的

trie用途介紹

trie是一種樹的結構,
用來儲存很多個字串
優點是它可以快速判斷一個字串是否在trie裡面(可以比BST還快),
但缺點是trie使用的空間消耗極大,
一個「以空間換取時間」的概念,
我的程式碼如下:

C++語言解- 120ms

class Trie {
    
    class TrieNode {
    public:
        vector<TrieNode *> child; //子節點有a~z共26種可能,初始設為null
        bool isWord; //記錄某點是否為單字的結尾
        TrieNode(): isWord(false), child(vector<TrieNode *>(26, NULL)) {};
    };
    
    TrieNode* root; //root為一個空的節點
    
public:
    /** Initialize your data structure here. */
    Trie(): root(new TrieNode()) {};
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode *p = root;
        for (char c : word) {
            int i = c - 'a';
            if (!p->child[i]){
                p->child[i] = new TrieNode();
            } 
            p = p->child[i];
        }
        p->isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word){
        TrieNode *p = root;
        for (char c : word) {
            int i = c - 'a';
            if (!p->child[i]){
                return false;
            }
            p = p->child[i];
        }
        return p->isWord;    
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode *p = root;
        for (char c : prefix) {
            int i = c - 'a';
            if (!p->child[i]){
                return false;
            } 
            p = p->child[i];
        }
        return true;        
    }
};

參考資料

  1. (youtube) 花花酱 LeetCode 208. Implement Trie (Prefix Tree) - 刷题找工作 EP73
  2. [LeetCode] 208. Implement Trie (Prefix Tree) 實現字典樹(前缀樹)
  3. 演算法筆記- 大量String資料結構:Trie

尚未有邦友留言

立即登入留言