<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:
    def __init__(self):
        _trie_init = lambda: defaultdict(_trie_init)
        self.root = _trie_init()

    def add_word(self, word, word_idx):
        curr = self.root
        for idx, c in enumerate(word):
            curr = curr[c]
            if 'children' not in curr:
                curr['children'] = []
            if idx < len(word) - 1 and Trie.is_palindrome(word, idx + 1, len(word) - 1):
                curr['children'].append((word_idx, word))
        curr['end'] = True
        curr['idx'] = word_idx

    def find_words(self, word):
        ans = []
        curr = self.root
        for idx, c in enumerate(word):
            if c not in curr:
                return ans
            curr = curr[c]
            if curr['end'] is True and Trie.is_palindrome(word, idx + 1, len(word) - 1):
                ans.append(curr['idx'])
        if 'children' in curr:
            ans.extend([word_idx for word_idx, _ in curr['children']])
        return ans

    @staticmethod
    def is_palindrome(word, start, end):
        while start < end:
            if word[start] != word[end]:
                return False
            start += 1
            end -= 1
        return True

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        ans = []

        for word_idx, word in enumerate(words):
            trie.add_word(word[::-1], word_idx)

        for word_idx, word in enumerate(words):
            matches = trie.find_words(word)
            for idx in matches:
                if idx == word_idx:
                    continue
                ans.append([word_idx, idx])

        if '' in words:
            empty_idx = words.index('')
            for idx, word in enumerate(words):
                if not Trie.is_palindrome(word, 0, len(word) - 1) or idx == empty_idx:
                    continue
                ans.extend([[idx, empty_idx], [empty_idx, idx]])

        return ans

140216