C++ Trie solution


  • 0
    X
    struct Trie{
            int n;
            unordered_map<char, Trie*> m;
            Trie(){
                n = 0;
            }
    };
    class WordDictionary {
    public:
        WordDictionary(){
            root = new Trie();
        }
        // Adds a word into the data structure.
        void addWord(string word) {
            Trie* tmp = root;
            for(int i = 0;i < word.length(); ++i){
                if(tmp->m.find(word[i]) == tmp->m.end()){
                    tmp->m[word[i]] = new Trie();
                }
                tmp = tmp->m[word[i]];
            }
            ++(tmp->n);
        }
        // Returns if the word is in the data structure. A word could
        // contain the dot character '.' to represent any one letter.
        bool search(string word) {
            return backtrack(root, 0, word);
        }
    private:
        Trie* root;
        bool backtrack(Trie* r, int p, string& word){
            if(p == word.length()){
                if(r->n > 0){
                    return true;
                }
                return false;
            }
            for(int i = p; i < word.length(); ++i){
                if(word[i] == '.'){
                    for(auto j = r->m.begin(); j != r->m.end(); ++j){
                        if(backtrack(j->second, p + 1, word)){
                            return true;
                        }
                    }
                    return false;
                }else if(r->m.find(word[i]) != r->m.end()){
                    return backtrack(r->m[word[i]], p + 1, word);
                }else{
                    return false;
                }
            }
            return false;
        }
    };

Log in to reply
 

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