Palindrome Pairs

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

• 0 <= i, j < words.length
• i != j
• words[i] + words[j] (the concatenation) is a palindrome

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

Examples

Example 1:

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

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

Explanation:

• words[0] + words[1] = "abcddcba" which is a palindrome.
• words[1] + words[0] = "dcbaabcd" which is a palindrome.
• words[2] + words[4] = "llssssll" which is a palindrome.
• words[3] + words[2] = "slls" which is a palindrome.

Example 2:

Input: words = ["bat","tab","cat"]

Output: [[0,1],[1,0]]

Explanation:

• words[0] + words[1] = "battab" which is a palindrome.
• words[1] + words[0] = "tabbat" which is a palindrome.

Example 3:

Input: words = ["a",""]

Output: [[0,1],[1,0]]

Explanation:

• words[0] + words[1] = "a" which is a palindrome.
• words[1] + words[0] = "a" which is a palindrome.

Constraints

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lowercase English letters
• All strings in words are unique