C++, My solution, easy to understand:)


  • 24
    C
        /**
         ** author: cxq
         ** weibo: http://weibo.com/chenxq1992
         **/ 
    
        class TrieNode {
        public:
            char content;   // the character included
            bool isend;     // if the node is the end of a word
            int shared;     // the number of the node shared ,convenient to implement delete(string key), not necessary in this problem
            vector<TrieNode*> children; // the children of the node
            // Initialize your data structure here.
            TrieNode():content(' '), isend(false), shared(0) {}
            TrieNode(char ch):content(ch), isend(false), shared(0) {}
            TrieNode* subNode(char ch) {
                if (!children.empty()) {
                    for (auto child : children) {
                        if (child->content == ch)
                            return child;
                    }
                }
                return nullptr;
            }
            ~TrieNode() {
                for (auto child : children)
                    delete child;
            }
        };
        
        class Trie {
        public:
            Trie() {
                root = new TrieNode();
            }
        
            // Inserts a word into the trie.
            void insert(string s) {
                if (search(s)) return;
                TrieNode* curr = root;
                for (auto ch : s) {
                    TrieNode* child = curr->subNode(ch);
                    if (child != nullptr) {
                        curr = child;
                    } else {
                        TrieNode *newNode = new TrieNode(ch);
                        curr->children.push_back(newNode);
                        curr = newNode;
                    }
                    ++curr->shared;
                }
                curr->isend = true;
            }
        
            // Returns if the word is in the trie.
            bool search(string key) {
                TrieNode* curr = root;
                for (auto ch : key) {
                    curr = curr->subNode(ch);
                    if (curr == nullptr)
                        return false;
                }
                return curr->isend == true;
            }
        
            // 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) {
                    curr = curr->subNode(ch);
                    if (curr == nullptr)
                        return false;
                }
                return true;
            }
            ~Trie() {
                delete root;
            }
        private:
            TrieNode* root;
        };

  • 0
    H

    Thanks for sharing! It's easy to understand.
    I think you could improve a little bit the insert() method. To be specific, the else {} section could be modified to the following:
    else {
    TrieNode *newNode = new TrieNode(ch);
    cur->children.push_back(newNode);
    cur = newNode;
    }

    The curr = curr->subNode(ch) is not necessary.


  • 0
    C

    Thanks for your advice! :)


  • 0
    Y

    you can use a special char as the end to save space.


  • 0
    W

    how long is your run time? I'm trying to find better solution with less than 60ms. Thanks.


  • 0
    K

    Excellent code! However, in your insert function, I think

    ++curr->shared;

    should be in the else part.


  • 0

    Since a new word is inserted, curr -> shared will always be incremented by 1.


  • 0

    Nice code! You even take many other factos (delete, destructor) into consideration.


  • 0
    C

    Your delete is not clear. To delete a tree, shouldn't we use dfs to delete every node? you just delete the root the the first level!


  • 0
    T

    Good to have destructors


  • 1
    Y

    I like your solution and I improve it a little bit.

      class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode(const char c) : m_char(c),m_is_end(false){}
        TrieNode():TrieNode(' '){}
        TrieNode* find_child(const char c) const{
            for(TrieNode* child: m_children){
                if(child->m_char == c) return child;
            }
            return nullptr;
        }
        ~TrieNode(){
            for(TrieNode* child: m_children) delete child;
        }
        char m_char;
        bool m_is_end;
        vector<TrieNode*> m_children;
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(const string & word) {
            TrieNode* curr = root;
            for (auto ch : word) {
                TrieNode* child = curr->find_child(ch);
                if (child != nullptr) {
                    curr = child;
                } else {
                    TrieNode *newNode = new TrieNode(ch);
                    curr->m_children.push_back(newNode);
                    curr = newNode;
                }
            }
            curr->m_is_end = true;//means one word end here
        }
    
        // Returns if the word is in the trie.
        bool search(const string & word) const {
            TrieNode* curr = find_root_node_with_prefix(word);
            if(!curr) return false;
            return curr->m_is_end == true;//one word end here or not
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(const string & prefix) const {
            TrieNode* curr = find_root_node_with_prefix(prefix);
            return curr == nullptr ? false : true;
        }
        //destructor
        ~Trie() {delete root;}
    protected:
        // return the root node of a prefix
        TrieNode* find_root_node_with_prefix(string prefix) const{
            TrieNode* curr = root;
            for (auto ch : prefix) {
                curr = curr->find_child(ch);
                if (curr == nullptr)
                    return nullptr;
            }
            return curr;
        }
    private:
        TrieNode* root;
    };
    

  • 0
    D

    @cxq1992 your implementation is great but just little bit concern about time complexity in search as you need to take O(n) in subNode to identify right child. This might be a okay trade-off between time. This might depend on the size of dictionary.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.