C++_Using Array_Accpeted_(Code for Deleting TrieNode also added)


  • 0

    Following is the code for this problem: very straightforward.

    class TrieNode {
    public:
    // Initialize your data structure here.
    TrieNode() {
        memset(children, NULL, sizeof(children));
    }
    TrieNode* children[26];
    bool isEnd = false;
    };
    
    class Trie {
    public:
    Trie() {
        root = new TrieNode();
    }
    
    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode* root_cpy = root;
        for(int i = 0; i < word.size(); ++i){
            int index = word[i] - 'a';
            if(root_cpy->children[index] == NULL){
                TrieNode* node = new TrieNode();
                root_cpy->children[index] = node;
            }
            root_cpy = root_cpy->children[index];
        }
        // the end (solider TrieNode)
        root_cpy->isEnd = true;
       }
    
    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode* root_cpy = root;
        for(int i = 0; i < word.size(); ++i){
            int index = word[i] - 'a';
            if(root_cpy->children[index] == NULL){return false;}
            root_cpy = root_cpy->children[index];
        }
        return root_cpy->isEnd;
    }
    
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode* root_cpy = root;
        for(int i = 0; i < prefix.size(); ++i){
            int index = prefix[i] - 'a';
            if(root_cpy->children[index] == NULL) return false;
            else{
                root_cpy = root_cpy->children[index];
            }
        }
        return true;
    }
    
    private:
    TrieNode* root;
    };
    

    Following is the entire code with delete operations, I write it in C++ with unordered_map

    #include <iostream>
    #include <string>
    #include <unordered_map>
    using namespace std;
    
    
    class TrieNode{
    public:
    unordered_map<char, TrieNode> children;
    bool isEnd;
    TrieNode(){//construction function
        children = *new unordered_map<char, TrieNode>();
        isEnd = false;
    }
    TrieNode(unordered_map<char, TrieNode> child, bool end){
        children = child;
        isEnd = end;
    }
    TrieNode(TrieNode& node):children(node.children), isEnd(node.isEnd){}
    ~TrieNode(){};
    };
    
    class Trie{
    public:
    TrieNode root; 
    Trie(){root = *new TrieNode();}
    Trie(Trie& trie):root(trie.root){}
    ~Trie(){};
    
    //insert
    void insert(string str){
        TrieNode cur = root;
        for(int i = 0; i < str.size(); ++i){
            char tmp = str[i];
            TrieNode node = cur.children[tmp];
            if(cur.children.find(tmp) == cur.children.end()){
                node = *new TrieNode();
                cur.children[tmp] = node;
            }
            cur = node;
        }
        cur.isEnd = true;
    }
    
    bool research(string str){
        return research_help(str, root, 0);
    }
    
    bool research_help(string str, TrieNode root, int start){
        if(start == str.size()) return root.isEnd;
        char tmp = str[start];
        if(root.children.find(tmp) == root.children.end()){
            return false;
        }
        TrieNode node = root.children[tmp];
        return research_help(str, node, start + 1);
    }
    
    void Delete(string str){
        Delete_help(str, root, 0);
    }
    
    bool Delete_help(string str, TrieNode root, int start){
        if(start == str.size()){
            //only when we reached the end of this word, we can delete this word
            if(root.isEnd == false){return false;}
        //if it is the end of this word, we just change isEnd to "false";
        root.isEnd = false;
        return root.children.empty();
        }
        
        char tmp = str[start];
        if(root.children.find(tmp) == root.children.end()) return false;
        TrieNode node = root.children[tmp];
        bool DeleteCurrentNode = Delete_help(str, node, start + 1);
        
        if(DeleteCurrentNode){
            root.children.erase(tmp);
            return root.children.empty();
        }
        return false;
    }
    
    bool startsWith(string str){
        return startsWith_help(str, root, 0);
    }
    
    bool startsWith_help(string str, TrieNode root, int start){
        if(start == str.size()){
            return true;
        }
        char tmp = str[start];
        if(root.children.find(tmp) == root.children.end()) return false;
        TrieNode node = root.children[tmp];
        return startsWith_help(str, node, start + 1);
    };
    };

Log in to reply
 

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