<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 Trie{
public:
    Trie * children[26];
    // int idx;
    int rev_idx;
    Trie():rev_idx(-1){
        fill(begin(children), end(children), nullptr);
    }
};
class Solution {
private:
    Trie * t;
    void add_words(string & word, int idx){
        int len=word.length();
        Trie * current=t;
        
        for(int i=len-1; i>=0; i--){
            if(current->children[word[i]-'a']==nullptr){
                current->children[word[i]-'a']=new Trie();
            }
            current=current->children[word[i]-'a'];
        }
        current->rev_idx=idx;
        
    }
    void dfs(Trie * current, vector<int>&idxs){
        if(current->rev_idx!=-1){
            idxs.push_back(current->rev_idx);
        }
        for(int i=0; i<26; i++){
            if(current->children[i]!=nullptr){
                dfs(current->children[i], idxs);
            }
        }
    }
    vector<int>search_idx(string &word, bool dir){
        int len=word.length();
        Trie * current=t;
        vector<int>idxs;
        for(int i=0; i<len; i++){
            if(current->rev_idx!=-1){
                idxs.push_back(current->rev_idx);
            }
            current=current->children[word[i]-'a'];
            if(current==nullptr){
                return idxs;
            }
        }
        dfs(current, idxs);
        return idxs;
    }
    bool is_palindrome(string & word1, string&word2){
        int len1=word1.length(), len2=word2.length();
        int start, end;
        
        if(len1>len2){
            start=len2;
            end=len1-1;
            while(start<end){
                if(word1[start++]!=word1[end--]){
                    return false;
                }
            }
        }
        else if(len1<len2){
            start=0;
            end=len2-len1-1;
            while(start<end){
                if(word2[start++]!=word2[end--]){
                    return false;
                }
            }

        }
        return true;
    }
    // void delete_trie(Trie * current){
    //     for(int i=0; i<26; i++){
    //         if(current->children[i]!=nullptr){
    //             delete_trie(current->children[i]);
    //         }
            
    //     }
    //     delete current;
    // }
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n=words.size();
        this->t=new Trie();
        for(int i=0; i<n; i++){
            add_words(words[i], i);
        }
        vector<vector<int>>res;
        for(int i=0; i<n; i++){
            int word_len=words[i].length();
            auto prefix=search_idx(words[i], true);
            
            for(int idx:prefix){
                if(idx==i){
                    continue;
                }
                if(is_palindrome(words[i],words[idx])){
                    res.push_back({i, idx});
                }
                // cout<<idx<<'\t';
            }
           
        }
        // delete_trie(t);
        return res;
    }
};
570634