Palindrome Pairs

Explanation & Solution

Description

You are given a 0-indexed array of unique strings words. A palindrome pair is a pair of integers (i, j) such that:

Return an array of all the palindrome pairs [i, j], sorted in ascending order.

Input:words = ["abcd","dcba","lls","s","sssll"]

abcd

dcba

lls

sssll

Output: [[0,1],[1,0],[2,4],[3,2]]

Explanation:

Trie pattern

Insert each word reversed into a trie
At each node during insertion, if the remaining prefix of the reversed word (i.e., the uninserted portion) is a palindrome, record the word's index in a palindromeSuffixes list at that node
At the end of each word insertion, mark the wordIndex and also add the index to palindromeSuffixes

For each word, traverse the trie character by character:
Case 1: If we hit a node with a wordIndex (a complete reversed word ends here) and the remaining suffix of the current word is a palindrome, then concatenating words[i] + words[wordIndex] forms a palindrome
Case 2: After fully traversing the current word in the trie, all indices in the current node's palindromeSuffixes list can form a palindrome pair with the current word

A helper function checks if a substring is a palindrome using the two-pointer technique
This is called during both trie building and searching

Inserting reversed words into the trie allows us to find pairs where one word is the reverse of a prefix/suffix of another
The palindromeSuffixes list captures cases where the leftover portion is itself a palindrome

Time

O(n * k^2) where n is the number of words and k is the average word length