<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 val;
     TrieNode* children[26];
     int stringNumber; //storinh the index of string in words array
    
    TrieNode(char ch){
        this->val = ch;
        for(int i =  0 ; i < 26; i++){
            children[i] = NULL;
        }
        this->stringNumber = -1;
    }
};

class Solution {
public: 
    void insertWord(TrieNode* root, string& word, int i, int& stringIndex){
        if(i >= word.length()){
            root->stringNumber = stringIndex;
            return;
        }

        char ch = word[i];
        int index = ch-'a';
        if(root->children[index] != NULL){
            insertWord(root->children[index], word, i+1, stringIndex);
        }
        else{
            TrieNode* child =  new TrieNode(ch);
            root->children[index] = child;
            insertWord(child, word, i+1,stringIndex);
        }
    }
    bool isPalindrome(string s, int i, int e){
        while(i<=e){
            if(s[i] != s[e]){
                return false;
            }
            i++;
            e--;
        }
        return true;
    }
    void solveCase2(TrieNode* root, vector<int>& myPalindrome , string s){
        
        if(root->stringNumber != -1){
            // string completed , check palindrome
            if(isPalindrome(s, 0, s.size()-1)){
                myPalindrome.push_back(root->stringNumber);
            }
        }

        for(int i = 0 ; i < 26; i++){
            //find all possibel string s
            if(root->children[i] != NULL){
                s.push_back(i +'a');
                solveCase2(root->children[i], myPalindrome, s);
                s.pop_back();
            }
        }
    }
    void search(TrieNode* root, string& word, vector<int>& myPalindrome ){
        //search in trie iteratively

        TrieNode* curr = root;
        //case-1
        for(int i = 0 ; i < word.size(); i++){
            int index = word[i] - 'a';
            if(curr->stringNumber != -1){
            //string has ended in trie;
            // a portion(or full) of word has been matched with a  full string of trie
            //check whether remianing of word is a palindrome , if yes then the 
            //matchedword + remWord + stringInTrie can be palindrome
            if(isPalindrome(word, i , word.size() - 1)){
                myPalindrome.push_back(curr->stringNumber);
            }
        }
            if(curr->children[index]){
                curr = curr->children[index];
            }
            else{
                return;
            }
        }

        // case2: word has ended , but not formed palindrome ,maybe after adding remaining string in
        //trie ->can become a palindrome ->check 
        solveCase2(curr, myPalindrome, "");
        //empty string because , we keep on building string , if we find end we check 
        //whetehr this generated string is palindrome , if yes, then add
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>>ans;
        TrieNode* root = new TrieNode('-');
        
        //insert all string in trie in reverseOrder
        for(int i  = 0 ; i < words.size(); i++ ){
            string reverseWord = words[i];
            reverse(reverseWord.begin(), reverseWord.end());
            insertWord(root, reverseWord, 0, i );
        }

        for(int i = 0 ; i < words.size(); i++){
            string searchWord = words[i];
            vector<int>myPalindrome; //store all palindrome index xorrespinding to ith word

            search(root, searchWord, myPalindrome);
            // add correspondig dtring number wrt ith string 
            for(int it : myPalindrome){
                if(it != i){
                    ans.push_back({i, it});
                }
            }
        }
        return ans;

        
    }
};
637864