Trie 字典樹 – 陪你刷題

Trie 是一種樹狀結構，可以用來在大量字串中快速搜尋某個字串。雖然這個問題也可以用 hash table 來解決，但在以下情況下，Trie 有其獨特的優勢：

找出每個有特定前綴的字串。
按照字典順序列出所有字串。

hash table 在面對上述問題時有兩個缺點：

如果大部分的輸入字串都具有相同的前綴，hash table 相對於 Trie 會耗費更多的記憶體空間。
hash table 可能會發生碰撞，導致搜尋的時間複雜度達到 O(n)，其中 n 是插入的總資料量；而 Trie 在執行搜尋時可以保持時間複雜度為 O(k)，其中 k 是搜尋字串的長度。

Trie 樹利用字串之間的共同前綴，將重複的前綴放在同一條路徑上，即可畫出如下圖的樹狀架構。

Trie 在現實生活中的應用相當常見，像是搜尋引擎的關鍵字建議或是 word 上的錯誤字訂正。

一般 Trie 資料結構會實現以下三個方法:

insert(word) : 插入一個新的字串。
search(word) : 尋找一個字串。
startWith(value) : 在 trie 內是否存在值為 value 的前綴。

以下來看兩題 Leetcode 範例：

Leetcode #208 Implement a Trie

Trie 的 root 是不含資料
每個 node 都包含一個 boolean 變數 isEndOfWord，紀錄該 node 是不是一個單字的結尾。

方法 1

有 constructor 和 Destructor ，該題討論區很多解答都沒有完整的這樣寫。
題目有說字串組成只包含小寫英文，可以直接透過 vector 劃分好大小。

class Trie {
private:
    struct TrieNode {
        bool isEndOfWord;
        TrieNode* children[26];

        TrieNode() : isEndOfWord(false) {
            for (int i = 0; i < 26; ++i) {
                children[i] = nullptr;
            }
        }
    };

    TrieNode* root;

    void deleteNode(TrieNode* node) {
        if (node == nullptr) return;
        for (int i = 0; i < 26; ++i) {
            if (node->children[i]) {
                deleteNode(node->children[i]);
            }
        }
        delete node;
    }

public:
    Trie() {
        root = new TrieNode();
    }

    ~Trie() {
        deleteNode(root);
    }

    void insert(const string& word) {
        TrieNode* curr = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (curr->children[index] == nullptr) {
                curr->children[index] = new TrieNode();
            }
            curr = curr->children[index];
        }
        curr->isEndOfWord = true;
    }

    bool search(const string& word) const {
        const TrieNode* node = findNode(word);
        return node != nullptr && node->isEndOfWord;
    }

    bool startsWith(const string& prefix) const {
        return findNode(prefix) != nullptr;
    }

private:
    const TrieNode* findNode(const string& str) const {
        const TrieNode* curr = root;
        for (char ch : str) {
            int index = ch - 'a';
            if (curr->children[index] == nullptr) {
                return nullptr;
            }
            curr = curr->children[index];
        }
        return curr;
    }
};

方法 2 Hash Table

如果節點內的資料只包含英文字母，當然採取方法 1 的 array 即可，但如果不僅限於單純英文字母，那採用 Hash table (以 c++ 來說，採用 unordered_map) 來維護可能的 child node 比較適合。

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode *curr = root;
        for (auto ch:word)
        {
            if (!curr->children.count(ch))
            {
                struct TrieNode *newNode = new TrieNode();
                curr->children[ch] = newNode;
            }
            curr = curr->children[ch];
        }
        curr->isEndOfWord = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode *curr = root;
        for (auto ch:word)
        {
            if (!curr->children.count(ch))
                return false;
            curr = curr->children[ch];
        }
        return curr->isEndOfWord;
    }
    /**
     * Returns if there is any word in the trie
     * that starts with the given prefix.
     */
    bool startsWith(string prefix) {
        TrieNode *curr = root;
        for (auto ch:prefix)
        {
            if (!curr->children.count(ch))
                return false;
            curr = curr->children[ch];
        }
        return true;
    }
private:
     struct TrieNode {
        bool isEndOfWord;
        unordered_map<char, TrieNode*> children;

        TrieNode() {
            isEndOfWord = false;
        }
        ~TrieNode() {
            for (auto child:children)
            {
                if (child.second) delete child.second;
            }
        }
    };
    TrieNode *root;
};

Leetcode #211 Design Add and Search Words Data Structure

這題為上一題的延伸，差別在於要處理特殊字元 '.' 。

方法 1 遞迴法

採取遞迴方式來 traverse 資料結構 Trie ，你也可以理解成是透過 DFS 來 traverse Trie 。
如果是遇到 '.' 這個特殊字元，所有存在的 node 都符合要求，都需要再往下做 DFS 。

class WordDictionary {
    struct TrieNode {
        bool isEndOfWord;
        unordered_map<char, TrieNode*> children;
        TrieNode () : isEndOfWord(false) { }
        ~TrieNode () {
            for (auto child:children)
            {
                if (child.second) delete child.second;
            }
        }
    };
    TrieNode *root = nullptr;
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new TrieNode ();
    }

    void addWord(string word) {
        TrieNode *curr = root;

        for (auto &ch:word)
        {
            if (curr->children.find(ch) == curr->children.end())
            {
                TrieNode *newNode = new TrieNode();
                curr->children[ch] = newNode;
            }
            curr = curr->children[ch];
        }
        curr->isEndOfWord = true;
    }

    bool search(string word) {
        return searchWord (0, word, root);
    }

    bool searchWord (int idx, string& word, TrieNode *curr)
    {
        if (idx == word.size())
            return curr->isEndOfWord;
        if (word[idx] == '.') {
            for (auto it=curr->children.begin(); it != curr->children.end(); it++) {
                if (searchWord(idx+1, word, it->second))
                    return true;
            }
        } else if (curr->children.find(word[idx]) != curr->children.end())
            return searchWord(idx+1, word, curr->children[word[idx]]);

        return false;
    }
};

Reference

208. Implement Trie (Prefix Tree) - Leetcode

Updated on 2024-07-13 22:39:18 星期六