In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

&nbsp;
Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"


Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"


&nbsp;
Constraints:


	1 &lt;= dictionary.length &lt;= 1000
	1 &lt;= dictionary[i].length &lt;= 100
	dictionary[i] consists of only lower-case letters.
	1 &lt;= sentence.length &lt;= 106
	sentence consists of only lower-case letters and spaces.
	The number of words in sentence is in the range [1, 1000]
	The length of each word in sentence is in the range [1, 1000]
	Every two consecutive words in sentence will be separated by exactly one space.
	sentence does not have leading or trailing spaces.


class Solution {
public:
    class trii{
        public:
        char data;
        trii* dict[26];
        bool isTerminal;
        
        trii(){
            
        }
        
        trii(char d){
           data=d;
            for(int i=0;i<26;i++){
                dict[i]=NULL;
            }
            isTerminal=false;
        }
    };
    
    class tree{
        public:
        trii* root;
        tree(){
            root=new trii('\0');
        }
        
        void insert(string str,trii* node){
            if(str.size()==0){
                node->isTerminal=true;
                return;
            }
            int index=str[0]-'a';
            if(node->dict[index]==NULL ){
                node->dict[index]=new trii(str[0]);
            }
            insert(str.substr(1),node->dict[index]);
        }
        
        string find(string str,trii* node,string pre){
            if( node->isTerminal==true ){
                return pre; 
            }            
            int index=str[0]-'a';
            if(str.size()==0 || node->dict[index]==NULL){
                return "\0";
            }
           return find(str.substr(1),node->dict[index],pre+str[0]);
        }
        
        string replaceWith(string word ,trii* node){
            string temp=find(word,node,"");
            if(temp!="\0"){
                word=temp;
            }
            return word;
        }
    };
    
    string replaceWords(vector<string>& dictionary, string sentence) {
       tree* t=new tree();
        for(int i=0;i<dictionary.size();i++){
            t->insert(dictionary[i],t->root);
        }
        string ans=sentence;
        sentence="";
        for(int i=0;i<ans.size();i++){
            string word="";
            while(i<ans.size()&&ans[i]!=' '){
                word+=ans[i];
                i++;
            }
            
            sentence+=t->replaceWith(word,t->root)+" ";
        }
        sentence.pop_back();
        return sentence;
    }
};
class Solution {
public:
    class trii{
        public:
        char data;
        trii* dict[26];
        bool isTerminal;
        
        trii(){
            
        }
        
        trii(char d){
           data=d;
            for(int i=0;i<26;i++){
                dict[i]=NULL;
            }
            isTerminal=false;
        }
    };
    
    class tree{
        public:
        trii* root;
        tree(){
            root=new trii('\0');
        }
        
        void insert(string str,trii* node){
            if(str.size()==0){
                node->isTerminal=true;
                return;
            }
            int index=str[0]-'a';
            if(node->dict[index]==NULL ){
                node->dict[index]=new trii(str[0]);
            }
            insert(str.substr(1),node->dict[index]);
        }
        
        string find(string str,trii* node,string pre){
            if( node->isTerminal==true ){
                return pre; 
            }            
            int index=str[0]-'a';
            if(str.size()==0 || node->dict[index]==NULL){
                return "\0";
            }
           return find(str.substr(1),node->dict[index],pre+str[0]);
        }
        
        string replaceWith(string word ,trii* node){
            string temp=find(word,node,"");
            if(temp!="\0"){
                word=temp;
            }
            return word;
        }
    };
    
    string replaceWords(vector<string>& dictionary, string sentence) {
       tree* t=new tree();
        for(int i=0;i<dictionary.size();i++){
            t->insert(dictionary[i],t->root);
        }
        string ans=sentence;
        sentence="";
        for(int i=0;i<ans.size();i++){
            string word="";
            while(i<ans.size()&&ans[i]!=' '){
                word+=ans[i];
                i++;
            }
            
            sentence+=t->replaceWith(word,t->root)+" ";
        }
        sentence.pop_back();
        return sentence;
    }
};
class Solution {
public:
    class trii{
        public:
        char data;
        trii* dict[26];
        bool isTerminal;
        
        trii(){
            
        }
        
        trii(char d){
           data=d;
            for(int i=0;i<26;i++){
                dict[i]=NULL;
            }
            isTerminal=false;
        }
    };
    
    class tree{
        public:
        trii* root;
        tree(){
            root=new trii('\0');
        }
        
        void insert(string str,trii* node){
            if(str.size()==0){
                node->isTerminal=true;
                return;
            }
            int index=str[0]-'a';
            if(node->dict[index]==NULL ){
                node->dict[index]=new trii(str[0]);
            }
            insert(str.substr(1),node->dict[index]);
        }
        
        string find(string str,trii* node,string pre){
            if( node->isTerminal==true ){
                return pre; 
            }            
            int index=str[0]-'a';
            if(str.size()==0 || node->dict[index]==NULL){
                return "\0";
            }
           return find(str.substr(1),node->dict[index],pre+str[0]);
        }
        
        string replaceWith(string word ,trii* node){
            string temp=find(word,node,"");
            if(temp!="\0"){
                word=temp;
            }
            return word;
        }
    };
    
    string replaceWords(vector<string>& dictionary, string sentence) {
       tree* t=new tree();
        for(int i=0;i<dictionary.size();i++){
            t->insert(dictionary[i],t->root);
        }
        string ans=sentence;
        sentence="";
        for(int i=0;i<ans.size();i++){
            string word="";
            while(i<ans.size()&&ans[i]!=' '){
                word+=ans[i];
                i++;
            }
            
            sentence+=t->replaceWith(word,t->root)+" ";
        }
        sentence.pop_back();
        return sentence;
    }
};
class Solution {
public:
    class trii{
        public:
        char data;
        trii* dict[26];
        bool isTerminal;
        
        trii(){
            
        }
        
        trii(char d){
           data=d;
            for(int i=0;i<26;i++){
                dict[i]=NULL;
            }
            isTerminal=false;
        }
    };
    
    class tree{
        public:
        trii* root;
        tree(){
            root=new trii('\0');
        }
        
        void insert(string str,trii* node){
            if(str.size()==0){
                node->isTerminal=true;
                return;
            }
            int index=str[0]-'a';
            if(node->dict[index]==NULL ){
                node->dict[index]=new trii(str[0]);
            }
            insert(str.substr(1),node->dict[index]);
        }
        
        string find(string str,trii* node,string pre){
            if( node->isTerminal==true ){
                return pre; 
            }            
            int index=str[0]-'a';
            if(str.size()==0 || node->dict[index]==NULL){
                return "\0";
            }
           return find(str.substr(1),node->dict[index],pre+str[0]);
        }
        
        string replaceWith(string word ,trii* node){
            string temp=find(word,node,"");
            if(temp!="\0"){
                word=temp;
            }
            return word;
        }
    };
    
    string replaceWords(vector<string>& dictionary, string sentence) {
       tree* t=new tree();
        for(int i=0;i<dictionary.size();i++){
            t->insert(dictionary[i],t->root);
        }
        string ans=sentence;
        sentence="";
        for(int i=0;i<ans.size();i++){
            string word="";
            while(i<ans.size()&&ans[i]!=' '){
                word+=ans[i];
                i++;
            }
            
            sentence+=t->replaceWith(word,t->root)+" ";
        }
        sentence.pop_back();
        return sentence;
    }
};
Replace Words