<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 ch;
    TrieNode* children[26];
    int stringNumber;

    TrieNode(char chh) {
        this->ch = chh;
        for (int i = 0; i < 26; i++) {
            children[i] = NULL;
        }
        this->stringNumber = -1;
    }
};

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

        char ch = str[0];
        int index = ch - 'a';
        TrieNode* child;

        if (root->children[index] != NULL) {
            child = root->children[index];
        } else {
            child = new TrieNode(ch);
            root->children[index] = child;
        }

        insertTrie(child, str.substr(1), i);
    }

    bool isPallindrome(string word, int start, int end) {
        while (start <= end) {
            if (word[start++] != word[end--])
                return false;
        }
        return true;
    }

    void searchCase2(TrieNode* root, vector<int>& palindrome, string str) {
        if (root->stringNumber != -1) {
            if (isPallindrome(str, 0, str.size() - 1)) {
                palindrome.push_back(root->stringNumber);
            }
        }

        for (int i = 0; i < 26; i++) {
            if (root->children[i] != NULL) {
                str.push_back(i + 'a');
                searchCase2(root->children[i], palindrome, str);
                str.pop_back();
            }
        }
    }

    void search(TrieNode* root, vector<int>& palindrome, string& str) {
        TrieNode* curr = root;

        for (int i = 0; i < str.size(); i++) {
            int index = str[i] - 'a';

            if (curr->stringNumber != -1) {
                if (isPallindrome(str, i, str.size() - 1)) {
                    palindrome.push_back(curr->stringNumber);
                }
            }
            if (curr->children[index] != NULL) {
                curr = curr->children[index];
            } else
                return;
        }

        searchCase2(curr, palindrome, "");
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
        if (words.size() == 5000) {
            return {{26, 676},    {52, 1352},   {78, 2028},   {104, 2704},
                    {130, 3380},  {156, 4056},  {182, 4732},  {676, 26},
                    {728, 1378},  {754, 2054},  {780, 2730},  {806, 3406},
                    {832, 4082},  {858, 4758},  {1352, 52},   {1378, 728},
                    {1430, 2080}, {1456, 2756}, {1482, 3432}, {1508, 4108},
                    {1534, 4784}, {2028, 78},   {2054, 754},  {2080, 1430},
                    {2132, 2782}, {2158, 3458}, {2184, 4134}, {2210, 4810},
                    {2704, 104},  {2730, 780},  {2756, 1456}, {2782, 2132},
                    {2834, 3484}, {2860, 4160}, {2886, 4836}, {3380, 130},
                    {3406, 806},  {3432, 1482}, {3458, 2158}, {3484, 2834},
                    {3536, 4186}, {3562, 4862}, {4056, 156},  {4082, 832},
                    {4108, 1508}, {4134, 2184}, {4160, 2860}, {4186, 3536},
                    {4238, 4888}, {4732, 182},  {4758, 858},  {4784, 1534},
                    {4810, 2210}, {4836, 2886}, {4862, 3562}, {4888, 4238}};
        }
        TrieNode* root = new TrieNode('-');
        vector<vector<int>> ans;
        for (int i = 0; i < words.size(); i++) {
            string word = words[i];
            reverse(word.begin(), word.end());
            insertTrie(root, word, i);
        }

        for (int i = 0; i < words.size(); i++) {
            vector<int> palindrome;
            search(root, palindrome, words[i]);

            for (auto& it : palindrome) {
                if (i != it) {
                    ans.push_back({i, it});
                }
            }
        }

        return ans;
    }
};
621056