#
# @lc app=leetcode id=336 lang=python3
#
# [336] Palindrome Pairs
#

# @lc code=start
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        wordict = {}
        res = []
        for i in range(len(words)):
            wordict[words[i]] = i
        for i in range(len(words)):
            for j in range(len(words[i]) + 1):
                tmp1 = words[i][:j]
                tmp2 = words[i][j:]
                if tmp1[::-1] in wordict and wordict[tmp1[::-1]] != i and tmp2 == tmp2[::-1]:
                    res.append([i, wordict[tmp1[::-1]]])
                if j != 0 and tmp2[::-1] in wordict and wordict[tmp2[::-1]] != i and tmp1 == tmp1[::-1]:
                    res.append([wordict[tmp2[::-1]], i])
        return res
# @lc code=end
