<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 Node:
    def __init__(self):
        self.adj = None
        self.isWord = False
        self.idx = -1
class Trie:
    def __init__(self):
        self.root = Node()
    def addWord(self, word, idx):
        def dfs(word, node, idx):
            if len(word) == 0:
                node.isWord = True
                node.idx = idx
                return
            if node.adj == None:
                node.adj = dict()
            if word[0] in node.adj:
                dfs(word[1:], node.adj[word[0]], idx)
            else:
                newNode = Node()
                node.adj[word[0]] = newNode
                dfs(word[1:], newNode, idx)
        dfs(word, self.root, idx)
    def prefix(self, word):
        ans = list()
        def isPalindrome(cur):
            return cur == cur[::-1]
        def getIdxs(node):
            ans = []
            def ddfs(node, cur):
                if node == None:
                    return
                if node.isWord:
                    if (isPalindrome(cur)):
                        ans.append(node.idx)
                if node.adj != None:
                    for k in node.adj:
                        ddfs(node.adj[k], cur + k)
            ddfs(node, "")
            return ans

        def dfs(word, node):
            if len(word) == 0:
                kk = getIdxs(node)
                for i in kk:
                    ans.append(i)
                return
            if node.isWord:
                if isPalindrome(word):
                    ans.append(node.idx)
            if node.adj == None:
                return False
            if word[0] in node.adj:
                dfs(word[1:], node.adj[word[0]])
            return False
        
        dfs(word, self.root)
        return ans
        
        

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        ans = []
        N = len(words)
        for i in range(N):
            trie.addWord(words[i], i)
        for i in range(N):
            idxs = trie.prefix(words[i][::-1])
            for _id in idxs:
                if _id != i:
                    ans.append([_id, i])
        return ans


        
117311