<p>You are given a <strong>0-indexed</strong> array of <strong>unique</strong> strings <code>words</code>.</p>

<p>A <strong>palindrome pair</strong> is a pair of integers <code>(i, j)</code> such that:</p>

<ul>
	<li><code>0 &lt;= i, j &lt; words.length</code>,</li>
	<li><code>i != j</code>, and</li>
	<li><code>words[i] + words[j]</code> (the concatenation of the two strings) is a <span data-keyword="palindrome-string">palindrome</span>.</li>
</ul>

<p>Return <em>an array of all the <strong>palindrome pairs</strong> of </em><code>words</code>.</p>

<p>You must write an algorithm with&nbsp;<code>O(sum of words[i].length)</code>&nbsp;runtime complexity.</p>

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

<pre>
<strong>Input:</strong> words = [&quot;abcd&quot;,&quot;dcba&quot;,&quot;lls&quot;,&quot;s&quot;,&quot;sssll&quot;]
<strong>Output:</strong> [[0,1],[1,0],[3,2],[2,4]]
<strong>Explanation:</strong> The palindromes are [&quot;abcddcba&quot;,&quot;dcbaabcd&quot;,&quot;slls&quot;,&quot;llssssll&quot;]
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;bat&quot;,&quot;tab&quot;,&quot;cat&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;battab&quot;,&quot;tabbat&quot;]
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;a&quot;,&quot;a&quot;]
</pre>

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

<ul>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>0 &lt;= words[i].length &lt;= 300</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
</ul>

class TrieNode{
     public:
     char value;
     TrieNode *children[26];
     int stringNumber;
     TrieNode(char ch):value(ch),stringNumber(-1)
     {
            for(int i=0;i<26;i++)
            children[i]=NULL;
     }
};
class Trie {
        void insertUtil(TrieNode *root, string &word, int i, int &stringNumber)
    {
           if(i>=word.size())
           {
                 root->stringNumber=stringNumber;
                 return;
           }
           int index=word[i]-'a';
           if(root->children[index]==NULL)
                 root->children[index]=new TrieNode(word[i]);
           insertUtil(root->children[index],word,i+1,stringNumber);
    }
public:

    TrieNode *root;
    Trie() {
        root =new TrieNode('\0');
    }
    
    void insert(string word, int &stringNumber) {
        insertUtil(root,word,0,stringNumber);
    }
    bool isPalindrom(string &s,int l, int h)
    {
          while(l<=h)
          {
              if(s[l] != s[h])   return false;
              l++;h--;
          }
          return true;
    }
    void search2(TrieNode *root, vector<int>&v, string s)
    {
            if(root->stringNumber != -1)
            {
                  if(isPalindrom(s,0,s.size()-1))
                     v.push_back(root->stringNumber);
            }
            for(int i=0;i<26;i++)
            {
                    if(root->children[i])
                    {
                          s.push_back(i+'a');
                          search2(root->children[i],v,s);
                          s.pop_back();
                    }
            }
    }
    void search(string &word,vector<int>&v) {
       TrieNode *curr=root;
       for(int i=0;i<word.size();i++)
       {
           int index=word[i]-'a';
           if(curr->stringNumber != -1)
           {
                  if(isPalindrom(word,i,word.size()-1)){
                      v.push_back(curr->stringNumber);
                  }
           }
           if(curr->children[index])
              {
                   curr=curr->children[index];
              }
           else 
           {
               return;
           }
       }
       search2(curr,v,""); 
    }
};
class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
               Trie trie;
        vector<vector<int>>ans;
        for(int i=0;i<words.size();i++)
        {
               string temp=words[i];
               reverse(temp.begin(),temp.end());
               trie.insert(temp,i);
        }
        for(int i=0;i<words.size();i++)
        {
              vector<int>v;
              trie.search(words[i],v);
              for(auto it:v)
              {
                  if(it != i)
                     ans.push_back({i,it});
              }
        }
        return ans;
    }
};
621056