# 回文对
给定一组 互不相同 的单词， 找出所有 不同 的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1：
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 ["battab","tabbat"]
示例 3：
输入：words = ["a",""]
输出：[[0,1],[1,0]]
提示：
1 <= words.length <= 50000 <= words[i].length <= 300words[i] 由小写英文字母组成
## template
```python
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
def is_palindrome(str, start, end):
"""检查子串是否是回文串
"""
part_word = str[start : end + 1]
return part_word == part_word[::-1]
def find_reversed_word(str, start, end):
"""查找子串是否在哈希表中
Return:
不在哈希表中，返回 -1
否则返回对应的索引
"""
part_word = str[start : end + 1]
ret = hash_map.get(part_word, -1)
return ret
hash_map = {}
for i in range(len(words)):
word = words[i][::-1]
hash_map[word] = i
res = []
for i in range(len(words)):
word = words[i]
word_len = len(word)
if is_palindrome(word, 0, word_len - 1) and "" in hash_map and word != "":
res.append([hash_map.get(""), i])
for j in range(word_len):
if is_palindrome(word, j, word_len - 1):
left_part_index = find_reversed_word(word, 0, j - 1)
if left_part_index != -1 and left_part_index != i:
res.append([i, left_part_index])
if is_palindrome(word, 0, j - 1):
right_part_index = find_reversed_word(word, j, word_len - 1)
if right_part_index != -1 and right_part_index != i:
res.append([right_part_index, i])
return res
```
## 答案
```python
```
## 选项
### A
```python
```
### B
```python
```
### C
```python
```