Solution - LeetCode 336. Palindrome Pairs | Hunter's Code

Solution - LeetCode 336. Palindrome Pairs | Hunter's Code

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:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]
Example 2:
Given words =["abcd", "dcba", "lls", "s", "sssll"]Return[[0, 1], [1, 0], [3, 2], [2, 4]]The palindromes are["dcbaabcd", "abcddcba", "slls", "llssssll"]`

The key point of this problem is to find whether each word in the given array has a substring which is a palindrome. If so, check other words one by one to see if the concatenation can be a palindrome; or find out a revserse word of the current one.

Therefore, we need to implement Manacher's algorithm of Longest Palindromic Substring

Also, we can use Trie structure, but…, anyway it's a good chance to learn this advanced structure right now.

However, I only come up with a brute force solution, which checks every pairs of words to see if the concatenation is a palindrome.

Read full article from Solution - LeetCode 336. Palindrome Pairs | Hunter's Code