<p>In English, we have a concept called <strong>root</strong>, which can be followed by some other word to form another longer word - let&#39;s call this word <strong>derivative</strong>. For example, when the <strong>root</strong> <code>&quot;help&quot;</code> is followed by the word <code>&quot;ful&quot;</code>, we can form a derivative <code>&quot;helpful&quot;</code>.</p>

<p>Given a <code>dictionary</code> consisting of many <strong>roots</strong> and a <code>sentence</code> consisting of words separated by spaces, replace all the derivatives in the sentence with the <strong>root</strong> forming it. If a derivative can be replaced by more than one <strong>root</strong>, replace it with the <strong>root</strong> that has <strong>the shortest length</strong>.</p>

<p>Return <em>the <code>sentence</code></em> after the replacement.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> dictionary = [&quot;cat&quot;,&quot;bat&quot;,&quot;rat&quot;], sentence = &quot;the cattle was rattled by the battery&quot;
<strong>Output:</strong> &quot;the cat was rat by the bat&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> dictionary = [&quot;a&quot;,&quot;b&quot;,&quot;c&quot;], sentence = &quot;aadsfasf absbs bbab cadsfafs&quot;
<strong>Output:</strong> &quot;a a b c&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

class TrieNode{
  public:
    char value;
    TrieNode* children[26];
    bool isTerminal;
    int ind;

    TrieNode(char val) {
      this->value = val;
      for(int i=0; i<26; i++) {
        children[i] = NULL;
      }
      this->isTerminal = false;
      this->ind=-1;
    }
};
//insertion
void insertWord(TrieNode* root, string word,int i) {
  //cout << "recieved word: " << word << " for insertion " << endl;
  //base case
  if(word.length() == 0) {
    root->isTerminal = true;
    root->ind=i;
    return;
  }

  char ch = word[0];
  int index = ch - 'a';
  TrieNode* child;
  if(root->children[index] != NULL) {
    //present
      child = root->children[index];
  }
  else {
    //absent
     child = new TrieNode(ch);
     root->children[index] = child;
  }

  //recursion
  insertWord(child, word.substr(1),i);

}

void searchWord(TrieNode* root, string word,int &k) {
  //base case
  if(root->isTerminal) {
    return;
  }

  char ch = word[0];
  int index;
  if(ch!=NULL){
    index = ch - 'a';
    TrieNode* child;
    if(root->children[index] != NULL) {
        //present or found
        child = root->children[index];
        k++;
    }
    else {
        //not found
        k=0;
        return;
    }

    ///baaaki recursion
    searchWord(child, word.substr(1),k);

  }
  else{
    return;
  }
   
  


   

}

void deleteWord(TrieNode* root, string word ) {
  if(word.length() == 0) {
    root->isTerminal = false;
    return;
  }

  //1 case mera
  char ch = word[0];
  int index = ch - 'a';
  TrieNode* child;

  if(root->children[index] != NULL) {
    //present
    child = root->children[index];
  }
  else{
    //not present
    return;
  }
  //baaki recursion tera
  deleteWord(child, word.substr(1));
}

void storeString(TrieNode* root, vector<pair<string,int>>& ans, string &input, string& prefix) {
  //base case
  if(root->isTerminal == true) {
    //ans store
    ans.push_back({prefix+input,root->ind});
    //return ?
  }

  for(char ch='a'; ch<='z'; ch++) {
    int index = ch - 'a';
    TrieNode* next = root->children[index];
    if(next != NULL) {
      //child exist
      input.push_back(ch);
      //baaaki recursion
      storeString(next, ans, input, prefix);
      //backtrack
      input.pop_back();
    }
  }
}

void findPrefixString(TrieNode* root, string input, vector<pair<string,int>>& ans, string &prefix) {
  //base case
  if(input.length() == 0) {
    TrieNode* lastchar = root;
    storeString(lastchar, ans, input, prefix);
    return;
  }
  char ch = input[0];
  int index = ch - 'a';
  TrieNode* child;
  if(root->children[index] != NULL) {
    //child present
    child = root->children[index];
  }
  else {
    return;
  }
  //recursive call
  findPrefixString(child, input.substr(1), ans, prefix);
}

// vector<vector<string> > getSuggestions(TrieNode* root, string input) {

//   vector<vector<string> > output;
//   TrieNode* prev = root;
//   string inputhelper = "";

//   for(int i=0; i<input.length(); i++) {
    // char lastchar = input[i];
    // int index = lastchar - 'a';
    // TrieNode* curr = prev->children[index];

    // if(curr == NULL) {
    //   break;
    // }
    // else {
    //   vector<string> nicheKaAns;
    //   inputhelper.push_back(lastchar);
    //   string dummy = "";
    //   storeString(curr, nicheKaAns, inputhelper, dummy);
    //   output.push_back(nicheKaAns);
      //important
//       prev = curr;
//     }

//   }
//   return output;
//}
class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        string element;
        vector<string>str;
        sentence.push_back(' ');
        for(int i=0;i<sentence.length();i++){
            if(sentence[i]==' '){
                str.push_back(element);
                element.clear();
            }
            else{
                element.push_back(sentence[i]);

            }
        }
        TrieNode*root=new TrieNode('-');
        for(int i=0;i<dictionary.size();i++){
            insertWord(root,dictionary[i],i);
        }
        int k=0;
        for(int i=0;i<str.size();i++){
            searchWord(root,str[i],k);
            if(k!=0){
                str[i]=str[i].substr(0,k);
            }
            k=0;
        }
        string realans;
        for(int i=0;i<str.size();i++){
            realans.append(str[i]);
            realans.append(" ");
        }
        realans.pop_back();
         
        return realans;



    }
};
220612