c++ Trie Tree solution easy to understand


  • 0
    Q
    class MagicDictionary {
    public:
        struct Trie{
            int val;
            bool isWord = false;
            Trie* child[26] = {};
            Trie(): isWord(false) {}
            Trie(int val1): isWord(false), val(val1) {}
        };
        Trie* root1;
        /** Initialize your data structure here. */
        MagicDictionary() {
            root1 = new Trie();
        }
        
        /** Build a dictionary through a list of words */
        void buildDict(vector<string> dict) {
            for(auto it:dict)
                gen(root1,it);
        }
        void gen(Trie* cur, string it){
            Trie* root = cur;
            for(int i=0;i<it.size();i++){
                int idx = it[i] - 'a';
                if(root->child[idx] == nullptr)
                    root->child[idx] = new Trie();
                root = root->child[idx];
            }
            root->isWord = true;
        }
        
        /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
        bool search(string word) {
            Trie* root = root1;
            int m = 0;
            for(int i=0;i<word.size();i++){
                int idx = word[i] - 'a';
                if(root->child[idx] != nullptr){
                    bool res = false;
                    for(int j=0;j<26;j++){
                        if(root->child[j]!= nullptr && j!=idx ){
                            string t = word.substr(i);
                            t[0] = j+'a';
                            res |= helper(t,root);
                        }
                    }
                    if(res == true)
                        return true;
                    root = root->child[idx];
                }
                else{
                    bool res = false;
                    for(int j=0;j<26;j++){
                        if(root->child[j]!= nullptr && j!=idx ){
                            string t = word.substr(i);
                            t[0] = j+'a';
                            res |= helper(t,root);
                        }
                    }
                    return res;
                }
            }
            return false;
        }
        
        bool helper(string s, Trie* cur){
            Trie* root = cur;
            for(int i=0;i<s.size();i++){
                int idx = s[i] - 'a';
                if(root->child[idx] == nullptr)
                    return false;
                root = root->child[idx];
            }
            return root->isWord;
        }
    };
    

Log in to reply
 

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