<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>

struct node{
    node *links[26];
    bool end = false;
    int index = -1;

    bool CheckRef(char ch){
        return links[ch - 'a']!= nullptr;
    }

    node* GetRef(char ch){
        return links[ch- 'a'];
    }

    void CreateRef(char ch, node * n){
        links[ch - 'a'] = n;
    }

    bool IsEnd(){
        return end;
    }

    void SetEnd(bool val){
        end = val;
    }

    int GetInd(){
        return index;
    }

    void SetInd(int val){
        index = val;
    }
};
class Solution {
    node * root = new node();
public:
    void searchWords(node* temp, vector<int>& indices) {
        if (temp->IsEnd()) {
            indices.push_back(temp->GetInd());
        }
        for (int i = 0; i < 26; ++i) {
            if (temp->links[i] != nullptr) {
                searchWords(temp->links[i], indices);
            }
        }
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
       auto Init = [&](){
            int index=0;
            for(const string  & str : words){
                node * temp = root;
                for(int i = str.size()-1 ;i >= 0 ; i--){
                    if(!temp->CheckRef(str[i])){
                        temp->CreateRef(str[i], new node());
                    }
                    temp = temp->GetRef(str[i]);
                }
                temp->SetEnd(true);
                temp->SetInd(index);
                index++;
            }
       };  

       Init();

       vector<vector<int>>res;

       auto Palli = [](const string& str, int left, int right) {
            while (left < right) {
                if (str[left++] != str[right--]) return false;
            }
            return true;
        };

       
       for (int i = 0; i < words.size(); ++i) {
            
            const string& word = words[i];
            node* trav = root;
            
            for (int j = 0; j < word.size(); ++j) {
            
                if (trav->IsEnd() && trav->GetInd() != i && Palli(word, j, word.size() - 1)) {
                    res.push_back({i, trav->GetInd()});
                }
                if (!trav->CheckRef(word[j])) {
                    trav = nullptr;
                    break;
                }
                trav = trav->GetRef(word[j]);
            }
            
            if (trav == nullptr) continue;
            
            vector<int> indices;
            searchWords(trav, indices);
            for (int ind : indices) {
                if (i != ind && Palli(words[ind], 0, words[ind].size() - word.size() - 1)) {
                    res.push_back({i, ind});
                }
            }
        }

        return res;
    }
};
562230