Palindrome Pairs

Return all pairs of different indices [i, j] such that words[i] + words[j] (joined in that order) is a palindrome. List the pairs sorted (by i, then j).

For ["abcd", "dcba", "lls", "s", "sssll"] the answer is [[0, 1], [1, 0], [2, 4], [3, 2]].

The starter code tests every pair. It is correct but too slow for many words.

Examples

Example 1

Input:

palindrome_pairs(['abcd', 'dcba', 'lls', 's', 'sssll'])

Output:

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

Example 2

Input:

palindrome_pairs(['bat', 'tab', 'cat'])

Output:

[[0, 1], [1, 0]]

Constraints

• 0 <= len(words) <= 3000
• 0 <= len(word) <= 12, lower-case letters; words may repeat and may be empty.