Trie Tree and stringstream,c++ ,bugfree


  • 0
    B
    class Solution {
    struct TreeNode{
        TreeNode* next[26];
        bool flag;
        TreeNode():flag(false){
            for(int i = 0;i < 26;i++) next[i] = nullptr;
        }
    };
    private:
        TreeNode *root = new TreeNode();
    public://trie树,author:qiuqian,bugfree
        string replaceWords(vector<string>& dict, string sentence) {
            stringstream ss(sentence);
            string tmp;
            vector<string> ret;
            string res = "";
            for(auto s:dict){
                buildTree(root,s);
            }
            while(ss >> tmp){
                string k = findminroot(root,tmp);
                ret.push_back(k);
            }
            for(int i = 0;i < ret.size();++i){
                if(i != 0) res += " ";
                res += ret[i];
            }
            return res;
        }
        string findminroot(TreeNode* root,string s){
            int i = 0;
            bool flag = false;
            for(;i < s.size();++i){
                if(root->next[s[i]-'a'] == nullptr || flag) break;
                root = root->next[s[i]-'a'];
                flag = root->flag;
            }
            return flag ? s.substr(0,i):s;
        }
        void buildTree(TreeNode* root,string s){
            for(int i = 0;i < s.size();++i){
                if(root->next[s[i]-'a'] == nullptr){
                    root->next[s[i]-'a'] = new TreeNode();
                }
                root = root->next[s[i]-'a'];
            }
            root->flag = true;
        }
    };

Log in to reply
 

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