<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:
    def __init__(self):
        self.head = {}
        self.answer = []

    def is_palindrome(self, word: str, front: int, back: int) -> bool:
        while front < back:
            if word[front] != word[back]: return False
            front += 1
            back -= 1
        return True
    
    def add_end_to_trie(self, node: dict, end_type: str, word_idx: int):
        if end_type not in node:
            node[end_type] = []
        node[end_type].append(word_idx)

    def add_ends_to_trie(self, word: str, ends: set[int], word_idx: int):
        front, cur = len(word), self.head
        while front > 0:
            if front in ends:
                self.add_end_to_trie(cur, "part_end", word_idx)
            front -= 1
            if word[front] not in cur:
                cur[word[front]] = {}
            cur = cur[word[front]]
        self.add_end_to_trie(cur, "true_end", word_idx)

    def add_to_answer(self, idx_a: int, b_indices: List[int]):
        for idx_b in b_indices:
            if idx_a != idx_b:
                self.answer.append([idx_a, idx_b])

    def search_trie(self, word: str, word_idx: int):
        front, cur = 0, self.head
        while front < len(word):
            # part end has to match with true end
            if "true_end" in cur and self.is_palindrome(word, front, len(word) - 1):
                self.add_to_answer(word_idx, cur["true_end"])
            if word[front] in cur:
                cur = cur[word[front]]
            else:
                return
            front += 1
        if front == len(word):
            self.add_to_answer(word_idx, cur.get("true_end", []))
            self.add_to_answer(word_idx, cur.get("part_end", []))


    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        # create trie
        for word_idx, word in enumerate(words):
            ends = set()
            for back in range(len(word)+1):
                if self.is_palindrome(word, 0, back-1):
                    ends.add(back)
            self.add_ends_to_trie(word, ends, word_idx)
        # add pairs to answer
        for word_idx, word in enumerate(words):
            self.search_trie(word, word_idx)
        return self.answer

94406