LeetCode - 208 解題紀錄

題目： LeetCode - 208. Implement Trie (Prefix Tree)

題目說明

建立一個 Prefix 字典樹 ( Trie )，並且完成某些功能。

解題思路

定義一個 class node 作為節點，裡面包含 node *child[26] 代表 26 個字母，isWord 代表走到這個 node 時是否形成一個單字。

• insert(string word)：
  定義一個 ptr，一開始指向 root，之後遍歷 word，逐一檢查對應的 child 是否存在，若不存在就新建。全部做完後 ptr 這時會指向最後一個字母的 node，再將 ptr->isWord 設為 True 即可。

• search(string word)：
  和 insert() 類似，只是當 child 不存在時就回傳 False。全部做完後，若 ptr->isWord 為 True 代表這個字串有被 insert() 進來，回傳 True，反之回傳 False。

• startsWith(string prefix)：
  和 search() 一模一樣，只是最後不需檢查 ptr->isWord，直接回傳 True 即可。

參考解法

// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

class node
{
public:
    node *child[26];
    bool isWord;
    node():isWord(false)
    {
        for(auto& p : child)
            p = nullptr;
    }
    ~node()
    {
        for(auto& p : child)
            delete p;
    }
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new node();
    }
    
    ~Trie()
    {
        delete root;
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        auto ptr = root;
        for(auto c : word)
        {
            int index = c - 'a';
            if(!ptr->child[index])
                ptr->child[index] = new node();
            ptr = ptr->child[index];
        }
        ptr->isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        auto ptr = root;
        for(auto c : word)
        {
            int index = c - 'a';
            if(!ptr->child[index])
                return false;
            ptr = ptr->child[index];
        }
        return ptr->isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        auto ptr = root;
        for(auto c : prefix)
        {
            int index = c - 'a';
            if(!ptr->child[index])
                return false;
            ptr = ptr->child[index];
        }
        return true;
    }
private:
    node* root;
};

2020-08-24 重寫

class TrieNode
{
public:
    TrieNode() : isWord(false) { for(auto& ptr : child) ptr = nullptr; }
    
    ~TrieNode() { for(auto& ptr : child) delete ptr; }
    
    void build(string& str, int idx)
    {
        if(idx == str.size()) { isWord = true; return; }
        if(!child[str[idx] - 'a']) child[str[idx] - 'a'] = new TrieNode();
        child[str[idx] - 'a']->build(str, ++idx);
    }
    
    bool search(string& str, int idx)
    {
        if(idx == str.size()) return isWord;
        return child[str[idx] - 'a'] ? child[str[idx] - 'a']->search(str, ++idx) : false;
    }
    
    bool prefix(string& str, int idx)
    {
        if(idx == str.size()) return true;
        return child[str[idx] - 'a'] ? child[str[idx] - 'a']->prefix(str, ++idx) : false;
    }
    
private:
    TrieNode* child[26];
    bool isWord;
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() { root = new TrieNode(); }
    
    ~Trie() { delete root; }
    
    /** Inserts a word into the trie. */
    void insert(string word) { root->build(word, 0); }
    
    /** Returns if the word is in the trie. */
    bool search(string word) { return root->search(word, 0); }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) { return root->prefix(prefix, 0); }
    
private:
    TrieNode* root;
};