字典树Trie树 + 深度优先遍历DFS

╰半夏微凉° 2022-05-26 11:49 174阅读 0赞

字典树是非常常见的数据结构，一定要学会使用。

这个很棒，在做char数组的DFS遍历的时候可能会用到，

这个时一定要学会手写的代码！！！！！

C++版本如下：

class TrieNode 
    {
    public:
        // Initialize your data structure here.
        TrieNode *child[26];
        bool isWord;
        TrieNode() : isWord(false) 
        {
            for (auto &a : child)
                a = NULL;
        }
    };
    
    class Trie 
    {
    public:
        Trie() 
        {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string s)
        {
            TrieNode *p = root;
            for (auto &a : s) {
                int i = a - 'a';
                if (p->child[i]==NULL)
                    p->child[i] = new TrieNode();
                p = p->child[i];
            }
            p->isWord = true;
        }
    
        // Returns if the word is in the trie.
        bool search(string key) 
        {
            TrieNode *p = root;
            for (auto &a : key) 
            {
                int i = a - 'a';
                if (p->child[i]==NULL)
                    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 (auto &a : prefix) 
            {
                int i = a - 'a';
                if (p->child[i]==NULL) 
                    return false;
                p = p->child[i];
            }
            return true;
        }
    
    private:
        TrieNode* root;
    };