<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* ch[26];
    bool isWord;
    int id;
    Trie() {
        for (int i = 0; i < 26; i++) {
            ch[i] = NULL;
        }
        isWord = false;
        id = -1;
    }
};
void insert(Trie *root, string& word, int& id) {
    for (int i = word.length() - 1; i >= 0; i--) {
        int c = word[i] - 'a';
        if (root->ch[c] == NULL) {
            root->ch[c] = new Trie();
        }
        root = root->ch[c];
    }
    root->isWord = true;
    root->id = id;
}

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        Trie *root = new Trie();
        for(int i = 0; i < words.size(); i++) {
            insert(root, words[i], i);
        }
        vector<vector<int>> res;
        for (int i = 0; i < words.size(); i++) {
            string word = words[i];
            if (word == "") {
                for (int k = 0; k < words.size(); k++) {
                    if (k != i && check(words[k], 0, words[k].length() - 1)) {
                        res.push_back({k, i});
                    }
                }
            }
            Trie *tmp = root;
            int j = 0;
            for (; j < word.length(); j++) {
                int c = word[j] - 'a';
                if (tmp->ch[c] == NULL) break;
                if (tmp->ch[c]->isWord == true) {
                    if (check(word, j + 1, word.length() -1) && i != tmp->ch[c]->id) {
                        res.push_back({i, tmp->ch[c]->id});
                    }
                }
                tmp = tmp->ch[c];
            }
            if (j == word.length() && tmp != NULL) { // keep finding
                string current = "";
                dfs(tmp, res, current, i);
            }
            
        }
        return res;
    }
    bool check(string & word, int s, int e) {
        while (s < e) {
            if (word[s] != word[e]) return false;
            s++;
            e--;
        }
        return true;
    }
    void dfs(Trie *root, vector<vector<int>> &res, string& current, int & id) {
        if (root == NULL) return;
        for (int i = 0; i < 26; i++) {
            if (root->ch[i] != NULL) {
                current += (i + 'a');
                if (root->ch[i]->isWord) {
                    if (check(current, 0, current.length() -1))  {
                        res.push_back({id, root->ch[i]->id});
                    }
                }
                dfs(root->ch[i], res, current, id);
                current.pop_back();
            }
            
        }
    }
};
562230