<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 {
// private:
// struct Trie{
//     public:
//     int end_idx;
//     Trie* children[26];
//     vector<int>palindrome_idxs;
//     Trie():end_idx(-1){
//         fill(begin(children), end(children), nullptr);
//         // this->end_idx=-1;
//     }
// };

//     Trie * t;
//     bool is_palindrome(string& word, int start, int end){
//         while(start<end){
//             if(word[start++]!=word[end--]){
//                 return false;
//             }
//             // start++;
//             // end--;
//         }
//         return true;
//     }
//     void add_words(Trie * current, vector<string>& words, int idx){
//         // string word=words[idx];
//         int len=words[idx].length();
//         // Trie * current=t;
//         for(int i=len-1; i>=0; i--){
//             int char_idx=words[idx][i]-'a';
//             if(current->children[char_idx]==nullptr){
//                 current->children[char_idx]=new Trie();
//             }
//             if(is_palindrome(words[idx], 0, i)){
//                 current->palindrome_idxs.push_back(idx);
//             }
//             current=current->children[char_idx];
//         }
//         current->palindrome_idxs.push_back(idx);
//         current->end_idx=idx;
//     }
//     void search_words(Trie * current, vector<vector<int>>&res, vector<string>& words, int idx){
//         // Trie* current=t;
//         // string word=words[idx];
//         int len=words[idx].length();
//         for(int i=0; i<len; i++){
//             int char_idx=words[idx][i]-'a';
//             if(current->end_idx>-1&&current->end_idx!=idx&&is_palindrome(words[idx], i, len-1)){
//                 res.push_back({idx, current->end_idx});
//             }
//             current=current->children[char_idx];
//             if(current==nullptr){
//                 return ;
//             }
//         }
//         for(int i:current->palindrome_idxs){
//             if(i!=idx){
//                 res.push_back({idx, i});
//             }
//         }
//     }
    
// public:
//     vector<vector<int>> palindromePairs(vector<string>& words) {
//         this->t=new Trie();
//         int n=words.size();
//         vector<vector<int>>res;
//         for(int i=0; i<n; i++){
//             this->add_words(t, words, i);
//         }
//         for(int i=0; i<n; i++){
//             this->search_words(t, res, words, i);
//         }
//         // delete_trie(t);
//         return res;
//     }
// };

class Solution {
public:
    
    // Trie implementation starts
    struct Node {
        struct Node *links[26];
        bool flag = false;
        int index = -1; // If flag is true, we store the index of string here
        
        bool isThere(char c){
            int val = c - 'a';
            
            if(links[val] != NULL)
                return true;
            return false;
        }
    };
    
    Node *root;

    void insert(string s, int i){ // Normal string insertion operation
        int n = s.length();
        
        Node *tmp = root;
        
        for(int i=0; i<n; i++){
            if(!tmp->isThere(s[i])){
                Node *t = new Node();
                tmp->links[s[i]-'a'] = t;
            }
            
            tmp = tmp->links[s[i] - 'a'];
        }
        
        tmp->flag = true;
        tmp->index = i;
    }
    
    // Trie implementation ends
    
    
    void dfs(Node *node, vector<int>&res){
        // From trie node '*node', adding all nodes below this node which have true as flag
        // ie. res is added up with all words possible from and below *node
        
        Node *t = node;
        
        if(t->flag == true)
            res.push_back(t->index);
        
        for(int i=0; i<26; i++){
            if(t->links[i] != NULL)
                dfs(t->links[i], res);
        }
    }
    
    
    // Trie actually contains all the reversed string of input words
    vector<int>search(string s){
        // We are finding 
        // Case 1) strings which are absolutely prefix of s in the trie,
        // Case 2) strings which are in trie having s as absolute prefix
        
        // For eg. if we search of s = "apple", if the trie has "app, bee, a, appled"
        // then app,a and appled's indices are added into res
        
        int n = s.length();
        
        Node *tmp = root;
        vector<int> res;
        
        for(int i=0; i<n; i++){
            if(tmp->flag == true)
                res.push_back(tmp->index);
            
            if(!tmp->isThere(s[i]))
                return res;
            
            tmp = tmp->links[s[i] - 'a'];
        }
           
        // doing a dfs to find other nodes (for case 2)
        dfs(tmp, res);
        
        return res;
    }

    bool isPalin(string a, string b){ // Checking if a+b is a palindrome
        string res = a + b;
        int l = 0;
        int r = res.size() - 1;
        
        while(l < r){
            if(res[l++] != res[r--])
                return false;
        }
        
        return true;
    }
    
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n = words.size();
        vector<vector<int>>res;
        
        root = new Node();
        
        for(int i=0; i<n; i++){
            string t = words[i];
            reverse(t.begin(), t.end());
            
            insert(t, i);
        }
        
    
        for(int i=0; i<n; i++){
            vector<int>t = search(words[i]);
            
            for(auto &val: t){
                if(val != i){
                    if(isPalin(words[i], words[val]))
                        res.push_back({i, val});
                }
            }
        }
        
        return res;
    }
};
688286