# 336. Palindrome Pairs

#### Hard

***

You are given a **0-indexed** array of **unique** strings `words`.

A **palindrome pair** is a pair of integers `(i, j)` such that:

* `0 <= i, j < word.length`,
* `i != j`, and
* `words[i] + words[j]` (the concatenation of the two strings) is a palindrome string.

Return *an array of all the **palindrome pairs** of* `words`.

&#x20;

**Example 1:**

<pre><code>Input: words = ["abcd","dcba","lls","s","sssll"]
<strong>Output:
</strong> [[0,1],[1,0],[3,2],[2,4]]
<strong>Explanation:
</strong> The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]
</code></pre>

**Example 2:**

<pre><code>Input: words = ["bat","tab","cat"]
<strong>Output:
</strong> [[0,1],[1,0]]
<strong>Explanation:
</strong> The palindromes are ["battab","tabbat"]
</code></pre>

**Example 3:**

<pre><code>Input: words = ["a",""]
<strong>Output:
</strong> [[0,1],[1,0]]
<strong>Explanation:
</strong> The palindromes are ["a","a"]
</code></pre>

&#x20;

**Constraints:**

* `1 <= words.length <= 5000`
* `0 <= words[i].length <= 300`
* `words[i]` consists of lowercase English letters.

```python
class Solution:
    def palindromePairs(self, words):
        # https://leetcode.com/problems/palindrome-pairs/discuss/2585442/Intuitive-Python3-or-HashMap-or-95-Time-and-Space-or-O(N*W2)
        d, res = dict([(w[::-1], i) for i, w in enumerate(words)]), []
        result = []
        for index, word in enumerate(words):
            if word in d and index != d[word]:
                result.append([index, d[word]])
            if word !="" and "" in d and word==word[::-1]:
                result.append([index,d[""]])
                result.append([d[""],index])
            for j in range(len(word)):
                if word[j:] in d and word[:j] == word[j-1::-1]:
                    result.append([d[word[j:]], index])
                if word[:j] in d and word[j:] == word[:j-1:-1]:
                    result.append([index, d[word[:j]]])
        return result
            
```