Sharing my c++ solution.


  • 0
    R
    #include <stdlib.h>
    #include <stdio.h>
    #include <iostream>
    #include <string>
    #include <tr1/unordered_map>
    using namespace std;
    using namespace std::tr1;
    class TrieNode {
        public:
            // Initialize your data structure here.
            TrieNode() {
            }
            bool has(char w){
                if(!_adj[w])
                    return false;
                else
                    return true;
            }
            TrieNode* get(char w) {
                if(!has(w))
                    return NULL;
                return _adj[w];
            }
            void add(char w,TrieNode* node) {
                _adj[w]=node;
            }
            bool isTail(){
                return has('#');
            }
        private:
            unordered_map<char,TrieNode*> _adj;
    };
    
    class Trie {
        public:
            Trie() {
                root = new TrieNode();
            }
    
            // Inserts a word into the trie.
            void insert(string s) {
                insert(s,getRoot());
            }
            void insert(string s,TrieNode* node) {
                if(s.length()==0) {
                    node->add('#',new TrieNode());
                    return;
                }
                char w=s[0];
                if(!node->has(w)) {
                    TrieNode* temp=new TrieNode();
                    node->add(w,temp);
                }
                int len=s.length();
                insert(s.substr(1,len-1),node->get(w));
            }
            bool search(string key,TrieNode* node,int tail) {
                int len=key.length();
                if(len==0) {
                    if(tail==1&&!node->isTail())
                        return false;
                    else
                        return true;
                }
                char w=key[0];
                if(!node->has(w))
                    return false;
                return search(key.substr(1,len-1),node->get(w),tail);
            }
            // Returns if the word is in the trie.
            bool search(string key) {
                if(key.length()==0)
                    return false;
                return search(key,getRoot(),1);
            }
    
            // Returns if there is any word in the trie
            // that starts with the given prefix.
            bool startsWith(string prefix) {
                if(prefix.length()==0)
                    return false;
                return search(prefix,getRoot(),0);
            }
            TrieNode* getRoot() {
                return root;
            }
        private:
            TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");
    void testSearch(Trie& trie,string s,int result)
    {
        if(trie.search(s)!=result) {
            cout<<"WA.Trie::search\t"<<s<<endl;
        }
    }
    void testStart(Trie& trie,string s,int result)
    {
        if(trie.startsWith(s)!=result) {
            cout<<"WA.Trie::Start\t"<<s<<endl;
        }
    }
    int main()
    {
        Trie trie;
        trie.insert("ab");
        testSearch(trie,"a",false);
        testStart(trie,"a",true);
        testSearch(trie,"ab",true);
        return 0;
    }

  • 0
    W

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


Log in to reply
 

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