<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 Solution {
public:
    struct trienode{
        int idx;
        trienode* ptr[26];
    };
    void create(trienode*& root,int idx,string& S,int id) {
        if(root == nullptr) {
            root = new(trienode);
            root->idx = -1;
            for(int i=0;i<26;i++) {
                root->ptr[i] = nullptr;
            }
        }
        if(idx == S.length()) {
            root->idx = id;
            return ;
        }
        create(root->ptr[S[idx] - 'a'],idx+1,S,id);
    }
    void palindromes(vector<string>& S,trienode* root,vector<vector<int>>& Sol,int maxLength) {
        //vector<vector<int>>A(maxLength,vector<int>(maxLength,0));
        vector<int>isPalindrome(maxLength,0);
        for(int idx = 0;idx < S.size();idx ++) {
            int n = S[idx].length();
            //vector<int>isPalindrome(n,0);
            for(int i=0;i<n;i++) {
                int l = 0,h = i;
                int a = 1;
                while(l <= h) {
                    if(S[idx][l] != S[idx][h]) {
                        a = 0;break;
                    }
                    l ++; h--;
                } 
                isPalindrome[i] = a;
            }
            for(int i=0;i<n;i++) {
                if(isPalindrome[i] == 1) {
                    int found = 1;
                    trienode* curr = root;
                    for(int j=n-1;j>i;j--) {
                        int k = S[idx][j] - 'a';
                        if(curr->ptr[k] != nullptr) {
                            curr = curr->ptr[k];
                        }
                        else {
                            found = 0;break;
                        }
                    }
                    if(found == 1 && curr->idx != idx && curr->idx != -1) {
                        Sol.push_back({curr->idx,idx});
                    }
                }
            }
            for(int i=n-1;i>=0;i--) {
                int l = i,h = n-1;
                int a = 1;
                while(l <= h) {
                    if(S[idx][l] != S[idx][h]) {
                        a = 0;break;
                    }
                    l ++; h--;
                } 
                isPalindrome[i] = a;
            }
            for(int i=n-1;i>=0;i--) {
                if(isPalindrome[i] == 1) {
                    trienode* curr = root;
                    int found = 1;
                    for(int j=i-1;j>=0;j--) {
                        int k = S[idx][j] - 'a';
                        if(curr->ptr[k] != nullptr) {
                            curr = curr->ptr[k];
                        }
                        else {
                            found = 0;break;
                        }
                    }
                    if(found == 1 && idx != curr->idx && curr->idx != -1) {
                        Sol.push_back({idx,curr->idx});
                    }
                }
            }
            trienode* curr = root;
            int found = 1;
            for(int i=n-1;i>=0;i--) {
                int k = S[idx][i] - 'a';
                if(curr->ptr[k] != nullptr) {
                    curr = curr->ptr[k];
                }
                else {
                    found = 0;break;
                }
            }
            if(found == 1 && curr->idx != -1 && curr->idx != idx) {
                Sol.push_back({idx,curr->idx});
            }
        }
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>>Sol;
        trienode* root = nullptr;
        int maxLength = 0;
        for(int i=0;i<words.size();i++) {
            create(root,0,words[i],i);
            if(maxLength < words[i].length()) maxLength = words[i].length();
        }
        palindromes(words,root,Sol,maxLength);
        return Sol;
    }
};
553826