# 336. Palindrome Pairs

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 < words.length`,
* `i != j`, and
* `words[i] + words[j]` (the concatenation of the two strings) is a palindrome.

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

You must write an algorithm with `O(sum of words[i].length)` runtime complexity.

&#x20;

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

&#x20;

**Constraints:**

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

分析

把每个word拆两段， 一段是回文的话， 只需要前后加入的词是另一段的回文即可

判断是否回文 内置函数快 word == word\[::-1]

```
# reversed suffix(w1) + prefix(is palindrome)+ suffix
# prefix + suffix(is palindrome) + reversed prefix(w1)
```

```
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        wordmap = {w:i for i, w in enumerate(words)}
        res = []      

        for i, w in enumerate(words):
            for j in range(len(w)+1):
                prefix = w[:j]
                suffix = w[j:]
               # reversed suffix(w1) + prefix(is palindrome)+ suffix
                if prefix == prefix[::-1]:
                    reversed_suffix = suffix[::-1]
                    if j>0 and reversed_suffix in wordmap and wordmap[reversed_suffix] != i:
                        res.append([wordmap[reversed_suffix], i])
                # prefix + suffix(is palindrome) + reversed prefix(w1)
                if suffix == suffix[::-1]:
                    reversed_prefix = prefix[::-1]
                    if reversed_prefix in wordmap and wordmap[reversed_prefix] != i:
                        res.append((i, wordmap[reversed_prefix]))
        return res



```