Palindrome Pairs

A palindrome reads the same forwards and backwards, like "racecar". Given a list of different words, write palindrome_pairs(words) that finds every pair of positions (i, j) with i != j where words[i] + words[j] is a palindrome.

Return the pairs as a list of tuples (i, j), sorted in increasing order (by i, then by j).

Examples

palindrome_pairs(['bat', 'tab', 'cat'])
# returns [(0, 1), (1, 0)]
palindrome_pairs(['abcd', 'dcba', 'lls', 's', 'sssll'])
# returns [(0, 1), (1, 0), (2, 4), (3, 2)]
palindrome_pairs(['a', ''])
# returns [(0, 1), (1, 0)]

In the second example "lls" + "sssll" gives "llssssll", and "s" + "lls" gives "slls". The empty string pairs both ways with every word that is a palindrome on its own.

Constraints

• 0 <= len(words) <= 5,000, and all words are different.
• Each word has 0 to 12 lowercase English letters.
• Trying every pair of words is far too slow for the largest lists.