[数据结构与算法]648. 单词替换——字典树

? ? ? ? 仍然是字典树，每一层的时候判断一下，如果有终止标记，意味着字典树中存在一个这样的前缀词，返回即可。

class Trim{
public:
    Trim* next[26];
    bool isEnd;

    Trim(){
        isEnd = false;
        memset(next,0,sizeof(next));
    }
};
class Solution {
public:
    void insert(Trim* t,string word){
        for(int i=0;i<word.size();i++){
            if(t->next[word[i]-'a']==NULL){
                t->next[word[i]-'a'] = new Trim();
            }
            t = t->next[word[i]-'a'];
        }
        t->isEnd = true;
    }

    string findminroot(Trim* t,string target){
        for(int i=0;i<target.size();i++){
            t = t->next[target[i]-'a'];
            if(t==NULL){
                return "!";
            }
            else if(t->isEnd==true){
                return target.substr(0,i+1);
            }
        }
        return t->isEnd?target:"!";
    }
    vector<string> stringsplit(string sen){
        int t=0;
        vector<string> res;
        for(int i=0;i<sen.size();i++){
            if(sen[i]==' '){
                res.push_back(sen.substr(t,i-t));
                t = i+1;
            }
        }
        res.push_back(sen.substr(t,sen.size()-t));
        return res;
    }
    string replaceWords(vector<string>& dictionary, string sentence) {
        Trim* t = new Trim();
        for(int i=0;i<dictionary.size();i++){
            insert(t,dictionary[i]);
        }
        vector<string> r = stringsplit(sentence);
        for(int i=0;i<r.size();i++){
            string result = findminroot(t,r[i]);
            if(result!="!"){
                r[i] = result;
            }
        }
        string res1 = "";
        bool flag= false;
        for(int i=0;i<r.size();i++){
            if(!flag){
                flag=true;
                res1 +=r[i];
            }
            else{
                res1+=" "+r[i];
            }
        }
        return res1;
    }
};