trie c++


  • 0
    Z
    class TrieNode{
    public:
        char content;
        bool isend;
        TrieNode* next[26];//a-z
        TrieNode():content('$'),isend(false){memset(next, 0, sizeof(next));}
        TrieNode(char x,bool flag):isend(flag){memset(next, 0, sizeof(next));}
    };
    class Trie{
    friend class Solution;
    public:
        Trie(){
            root=new TrieNode();
        }
        void insertWord(TrieNode*root,string word){
            auto curr=root;
            for(auto c:word){
                if(!curr->next[c-'a']) curr->next[c-'a']=new TrieNode(c,0);
                curr=curr->next[c-'a'];
            }
            curr->isend=1;
        }
        void findPrefix(TrieNode* root,string word,string& res){
            if(! root) return ;
            auto curr=root;
            for(auto x:word){
                curr=curr->next[x-'a'];
                res.push_back(x);
                if(!curr){
                    res=word;
                    return ;
                }            
                if(curr->isend) return ;
           
            }
        }
    private:
        TrieNode* root;
    };
    
    class Solution {
    public:
        string replaceWords(vector<string>& dict, string sentence) {
            if(dict.empty()) return sentence;
            Trie dic;
            for(auto x:dict)
                dic.insertWord(dic.root,x);
            vector<string> cutWord=split(sentence," ");
            string ans;
            for(auto &x:cutWord){
                string res;
                dic.findPrefix(dic.root,x,res);
                ans+=(res+" ");
            }
            //for(auto x:cutWord) cout<<x<<" ";
            ans.pop_back();
            return ans;
      
        }
        vector<string> split(const string& input,const string& split_character){
            vector<string> res;
            int split_len=split_character.size(),start=0;
            for(int i=0;i<input.size();++i){
                if(input.substr(i,split_len)==split_character){
                    res.push_back(input.substr(start,i-start));
                    start=i+split_len;
                }
            }
            
            res.push_back(input.substr(start,input.size()-start));
            return res;
        }    
    };
    

Log in to reply
 

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