With respect to a given <code>puzzle</code> string, a <code>word</code> is <em>valid</em> if both the following conditions are satisfied:
<ul>
	<li><code>word</code> contains the first letter of <code>puzzle</code>.</li>
	<li>For each letter in <code>word</code>, that letter is in <code>puzzle</code>.
	<ul>
		<li>For example, if the puzzle is <code>&quot;abcdefg&quot;</code>, then valid words are <code>&quot;faced&quot;</code>, <code>&quot;cabbage&quot;</code>, and <code>&quot;baggage&quot;</code>, while</li>
		<li>invalid words are <code>&quot;beefed&quot;</code> (does not include <code>&#39;a&#39;</code>) and <code>&quot;based&quot;</code> (includes <code>&#39;s&#39;</code> which is not in the puzzle).</li>
	</ul>
	</li>
</ul>
Return <em>an array </em><code>answer</code><em>, where </em><code>answer[i]</code><em> is the number of words in the given word list </em><code>words</code><em> that is valid with respect to the puzzle </em><code>puzzles[i]</code>.
<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;aaaa&quot;,&quot;asas&quot;,&quot;able&quot;,&quot;ability&quot;,&quot;actt&quot;,&quot;actor&quot;,&quot;access&quot;], puzzles = [&quot;aboveyz&quot;,&quot;abrodyz&quot;,&quot;abslute&quot;,&quot;absoryz&quot;,&quot;actresz&quot;,&quot;gaswxyz&quot;]
<strong>Output:</strong> [1,1,3,2,4,0]
<strong>Explanation:</strong> 
1 valid word for &quot;aboveyz&quot; : &quot;aaaa&quot; 
1 valid word for &quot;abrodyz&quot; : &quot;aaaa&quot;
3 valid words for &quot;abslute&quot; : &quot;aaaa&quot;, &quot;asas&quot;, &quot;able&quot;
2 valid words for &quot;absoryz&quot; : &quot;aaaa&quot;, &quot;asas&quot;
4 valid words for &quot;actresz&quot; : &quot;aaaa&quot;, &quot;asas&quot;, &quot;actt&quot;, &quot;access&quot;
There are no valid words for &quot;gaswxyz&quot; cause none of the words in the list contains letter &#39;g&#39;.
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;apple&quot;,&quot;pleas&quot;,&quot;please&quot;], puzzles = [&quot;aelwxyz&quot;,&quot;aelpxyz&quot;,&quot;aelpsxy&quot;,&quot;saelpxy&quot;,&quot;xaelpsy&quot;]
<strong>Output:</strong> [0,1,3,2,0]
</pre>

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

<ul>
	<li><code>1 &lt;= words.length &lt;= 10<sup>5</sup></code></li>
	<li><code>4 &lt;= words[i].length &lt;= 50</code></li>
	<li><code>1 &lt;= puzzles.length &lt;= 10<sup>4</sup></code></li>
	<li><code>puzzles[i].length == 7</code></li>
	<li><code>words[i]</code> and <code>puzzles[i]</code> consist of lowercase English letters.</li>
	<li>Each <code>puzzles[i] </code>does not contain repeated characters.</li>
</ul>

class Solution {
  
  struct TrieNode {
    struct TrieNode* children[26];
    int ew;  //word end
};
  
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
      
      struct TrieNode* root = getNode();
      
      /* 
      Insert each word[i] in Trie,Then for each puzzles[i] search in Trie
      
      There is no need to insert duplicate chars of word, also order of char in a word do not matter , so insert each word in trie in sorted order without any duplicate
      
      To do this , first insert each chars of a word in a set 
      */
      
      for(string& s:words){
        set<char>st;  //using set to avoid duplicates as well as word also get sorted
        
        st.insert(s.begin(),s.end());
        
        string sorted_str="";
        for(char ch:st)
          sorted_str+=ch;
        
        insert(root,sorted_str);
          
    }
      
    /*
        after removing duplicates and sorting
  (a,as,abel,abilty,act,acort,aces) -> Present in Trie
  
    Also while searching the count of words corresponding to puzzles[i], first we need to check presence of first char of puzzles[i], order of chars not matters, so we store the first char and sort the puzzles[i]
    
  Now lets search for count of words corresponds to actresz-> sorted(acerstz) , First_ch=a
  
  for(acerstz){
  a==First_ch (true) , move toward a , count=count+count of ew(at 'a')= 0+1=1
  c(First_ch 'a' already get(true)) , a->c(in trie) , count=count+count of ew(at 'c')=1+0=1
  e , a->c->e(in trie) , count=count+count of ew( at 'e')=1+0=1
  r , a->c->e->r , count=count + count of ew(at 'r')=1+0=1
  s , a->c->e->r->s, count=count+ count of ew (at 's')= 1+2(for "as" and "aces")=3
  t , a->c->e->r->s->t , count=count+ count of ew(at 't')=3+1(for "act")=4
  z , a->c->e->r->s->t->z , count=count+ count of ew (at 'z')= 4+0=4
  
  return count=4;
  
  }

    
    */
      
      vector<int>count;
      for(string puzz:puzzles){
        char first_ch=puzz[0];
        sort(puzz.begin(),puzz.end());
        
        int c=0;
        c= search(root,puzz,first_ch,false);
        count.push_back(c);
        
      }
      return count; 
    }
  
          
struct TrieNode* getNode(void)
{

    struct TrieNode* pNode = new TrieNode;
    pNode->ew= 0;
  
    for (int i = 0; i < 26; i++)
        pNode->children[i] = NULL;
 
    return pNode;
}
 
  
void insert(struct TrieNode* root, string key)
{
    struct TrieNode* pCrawl = root;
  
   for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
     
        pCrawl = pCrawl->children[index];
    }
  
    pCrawl->ew +=1;
}
  

int search(struct TrieNode* root, string str,char first_ch,bool firstSeen)
{
    if(!root)
        return 0;
    
    int count = 0;

    if(firstSeen)
        count += root->ew;
    
    for(int i = 0; i < str.length(); i++)
    {
       int index=str[i]-'a';
        if(str[i] == first_ch)
            count += search(root->children[index], str, first_ch,true);
        else
            count += search(root->children[index], str,first_ch,firstSeen);
    }

    return count;
}

};
166900