Palindrome pairs

Given a list of distinct words, return every pair of indices (i, j) where words[i] + words[j] is a palindrome. Checking all pairs is too slow; put the reversed words in a hash map (or a trie) and for each word try each split into a prefix and suffix, looking for the missing reversed piece when the other part is a palindrome.