Palindrome Pairs

For words[i] + words[j] to be a palindrome, check: reverse(words[j]) == words[i] prefix with words[i] suffix being a palindrome, or vice versa.

Store reversed words in a Trie (with word indices at end nodes).

For each word, walk the Trie: if you exhaust the word first, check if remaining Trie path is a palindrome; if you exhaust the Trie first, check if remaining word suffix is a palindrome.