Using recursive in c++ with detailed explanation


  • 2
    A

    I do not solve the problem at first sight, even I do not know what trie is ,but I find a good passage which describe the trie clearly.and I also see the pseudo code,I just implement by c++.here is the link:
    https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/

        class TrieNode {
    public:
        // Initialize your data structure here.
        TrieNode() {
                words=0;
                prefixs=0;
                for(int i=0;i<26;i++)
                   edges[i]=NULL; 
            }
            int words;
            int prefixs;
            TrieNode* edges[26];
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
                insertHelper(root,word,0);
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
                return searchHelper(root,word,0)!=0;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
                return startsWithHelper(root,prefix,0)!=0;
        }
        
        void insertHelper(TrieNode * node,string &word,int pos) {
            if(pos==word.size())
            {
                node->words++;
                node->prefixs++;
            }
            else
            {
                node->prefixs++;
                int char_code=word[pos]-'a';
                if(node->edges[char_code]==NULL)
                    node->edges[char_code]=new TrieNode();
                insertHelper(node->edges[char_code],word,pos+1);
            }
        }
        
        int searchHelper(TrieNode * node,string &word,int pos)
        {
            int char_code=word[pos]-'a';
            if(pos==word.size())
                return node->words;
            else if(node->edges[char_code]==NULL)
                return 0;
            else 
                return searchHelper(node->edges[char_code],word,pos+1);
        }
        
        int startsWithHelper(TrieNode * node,string &word,int pos)
        {
            int char_code=word[pos]-'a';
            if(pos==word.size())
                return node->prefixs;
            else if(node->edges[char_code]==NULL)
                return 0;
            else
                return startsWithHelper(node->edges[char_code],word,pos+1);
        }
    
    private:
        TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");
    

    I also translate the passage to Chinese:
    http://blog.csdn.net/u012501459/article/details/46741267


Log in to reply
 

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