<h3><a title="题目描述" href="https://leetcode-cn.com/problems/palindrome-pairs/">题目描述</a></h3>
<h4>方法一:哈希树</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">class Solution:
def palindromePairs1(self, words: List[str]) -> List[List[int]]:
# 核心思想--枚举前缀和后缀
# 如果两个字符串k1，k2组成一个回文字符串会出现三种情况
# len(k1) == len(k2),则需要比较k1 == k2[::-1]
# len(k1) < len(k2),例如，k1=a, k2=abb,可组成abba
# 因为k2后缀bb已经是回文字符串了，则需要找k1与k2剩下相等的部分
# len(k1) > len(k2),例如，k1=bba, k2=a,组成abba
# 因为k1前缀bb已经是回文字符串了，则需要找k1剩下与k2相等的部分
res = []
worddict = {word: i for i, word in enumerate(words)} # 构建一个字典，key为word，valie为索引
for i, word in enumerate(words):
# i为word索引，word为字符串
for j in range(len(word)+1):
# 这里+1是因为，列表切片是前闭后开区间
tmp1 = word[:j] # 字符串的前缀
tmp2 = word[j:] # 字符串的后缀
if tmp1[::-1] in worddict and worddict[tmp1[::-1]] != i and tmp2 == tmp2[::-1]:
# 当word的前缀在字典中，且不是word自身，且word剩下部分是回文(空也是回文)
# 则说明存在能与word组成回文的字符串
res.append([i, worddict[tmp1[::-1]]]) # 返回此时的word下标和找到的字符串下标
if j > 0 and tmp2[::-1] in worddict and worddict[tmp2[::-1]] != i and tmp1 == tmp1[::-1]:
# 当word的后缀在字典中，且不是word自身，且word剩下部分是回文(空也是回文)
# 则说明存在能与word组成回文的字符串
# 注意：因为是后缀，所以至少要从word的第二位算起，所以j>0
res.append([worddict[tmp2[::-1]], i]) # 返回此时的word下标和找到的字符串下标
return res
</pre>
<p> </p>
<h4>自己写的暴力方法，会超时</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
res = []
for i in range(len(words)):
for j in range(len(words)):
if(i != j):
temp = words[i] + words[j]
if(self.helper(temp)):
res.append([i,j])
return res
def helper(self,string):
if not string:
return True
left, right = 0, len(string) - 1
while(left < right):
if(string[left] != string[right]):
return False
left += 1
right -= 1
return True
</pre>
<p> </p>
## 思路：
### [官方题解](https://leetcode-cn.com/problems/palindrome-pairs/solution/hui-wen-dui-by-leetcode-solution/ "官方题解")
Leetcode336 回文对
