1
class Solution {
2
public:
3
    class trii{
4
        public:
5
        char data;
6
        trii* dict[26];
7
        bool isTerminal;
8

9
        trii(){
10

11
        }
12

13
        trii(char d){
14
           data=d;
15
            for(int i=0;i<26;i++){
16
                dict[i]=NULL;
17
            }
18
            isTerminal=false;
19
        }
20
    };
21

22
    class tree{
23
        public:
24
        trii* root;
25
        tree(){
26
            root=new trii('\0');
27
        }
28

29
        void insert(string str,trii* node){
30
            if(str.size()==0){
31
                node->isTerminal=true;
32
                return;
33
            }
34
            int index=str[0]-'a';
35
            if(node->dict[index]==NULL ){
36
                node->dict[index]=new trii(str[0]);
37
            }
38
            insert(str.substr(1),node->dict[index]);
39
        }
40

41
        string find(string str,trii* node,string pre){
42
            if( node->isTerminal==true ){
43
                return pre; 
44
            }            
45
            int index=str[0]-'a';
46
            if(str.size()==0 || node->dict[index]==NULL){
47
                return "\0";
48
            }
49
           return find(str.substr(1),node->dict[index],pre+str[0]);
50
        }
51

52
        string replaceWith(string word ,trii* node){
53
            string temp=find(word,node,"");
54
            if(temp!="\0"){
55
                word=temp;
56
            }
57
            return word;
58
        }
59
    };
60

61
    string replaceWords(vector<string>& dictionary, string sentence) {
62
       tree* t=new tree();
63
        for(int i=0;i<dictionary.size();i++){
64
            t->insert(dictionary[i],t->root);
65
        }
66
        string ans=sentence;
67
        sentence="";
68
        for(int i=0;i<ans.size();i++){
69
            string word="";
70
            while(i<ans.size()&&ans[i]!=' '){
71
                word+=ans[i];
72
                i++;
73
            }
74

75
            sentence+=t->replaceWith(word,t->root)+" ";
76
        }
77
        sentence.pop_back();
78
        return sentence;
79
    }
80
};
81