My simple c++ solution


  • 0
    K
    class TrieNode {
    public:
    bool End=false;
    vector<TrieNode *>list;
    TrieNode() {
        list.resize(26);
    }
     void setEnd(){
        End=true;
    }
    bool isEnd(){ return End; }
    void put(char ch, TrieNode * node){
        list[ch-'a']=node;
    }
    TrieNode * get(char ch){return list[ch-'a'];}
    bool contain(char ch){
        return list[ch-'a']!=NULL;
    }
    };
    class WordDictionary {
    private: 
    TrieNode * root;
    public:
    WordDictionary(){
        root=new TrieNode();
    }
    
    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode * node=root;
        for(int i=0; i < word.length(); i++){
            char ch=word[i];
            if(!node->contain(ch))node->put(ch, new TrieNode());
            node=node->get(ch);
        }
        node->setEnd();
    }
    
    // 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 helper(root, word, 0);
    }
    bool helper(TrieNode * node, string word, int pos){
        if(node==NULL)return false;
        if(pos==word.length())return node->isEnd();
        char ch=word[pos];
        if(ch=='.'){
            for(int i=0; i < 26; i++){
                if(node->contain('a'+i)){
                    if(helper(node->get('a'+i), word, pos+1))return true;
                }
            }
            return false;
        }
        else return helper(node->get(ch), word, pos+1);
    }
    };

Log in to reply
 

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