# Question

Formatted question description: https://leetcode.ca/all/336.html

 336. Palindrome Pairs

Given a list of unique words, find all pairs of distinct indices (i, j) in the given list,
so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:

Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]

@tag-trie



# Algorithm

step1: put the reverse order of the words into a map

step 2 & 3: check the prefix of each word.

It can form a palindrome iff

• prefix in the map AND
• rest substring is a palindrome.

e.g. “abll”, if the prefix is ab, and the map contains a “ab”, then we can form a palindrome which is abllba

Check the postfix of each word. The word can form a palindrome iff

• postfix is in the map AND
• the rest of prefix is a palindrome e.g. “llab”, where the postfix is ab, if the map cotnains a “ab”, then we can form a palindrome of ballab

Java