LeetCode208—Implement Trie (Prefix Tree)

﹏ヽ暗。殇╰゛Y 2022-07-13 13:52 152阅读 0赞

# 原题 #

看了[WIKI][]才知道怎么回事。

[原题链接][Link 1]

> Implement a trie with insert, search, and startsWith methods.
> 
> Note:  
> You may assume that all inputs are consist of lowercase letters a-z.

# 分析 #

实现一个前缀树/字典树  
要求实现插入、查找、前缀查找

class TrieNode {
        public:
        unordered_map<char ,TrieNode *>children;
        bool isLeaf;
        // Initialize your data structure here.
        TrieNode():isLeaf(false) 
        {
        }
    };
    
    class Trie {
        public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            int length= word.size();
            TrieNode*p=root;
            for(int i=0;i<length;++i)
            {
            if(p->children.find(word[i])==p->children.end())
                p->children[word[i]]=new TrieNode();
            p=p->children[word[i]];
            }
            p->isLeaf=true;
    
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
            TrieNode*p=root;
            int length=word.size();
            for(int i=0;i<length;++i)
            {
            if(p->children.find(word[i])==p->children.end())
                return false;
            p=p->children[word[i]];
            }
            if(NULL!=p&&p->isLeaf)
            return true;
            else
            return false;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            TrieNode*p=root;
            int length=prefix.size();
            for(int i=0;i<length;++i)
            {
            if(p->children.find(prefix[i])==p->children.end())
                return false;
    
            p=p->children[prefix[i]];
            }
            return true;
    
        }
    
        private:
        TrieNode* root;
    };

[WIKI]: https://www.google.com/search?q=Trie&oq=Trie&aqs=chrome.0.69i59j69i60l2j69i59j69i60l2.1312j0j7&sourceid=chrome&ie=UTF-8
[Link 1]: https://leetcode.com/problems/implement-trie-prefix-tree/