1240. Palindrome Pairs

Given a list of distinct words, find every pair of indices (i, j) with i != j such that the concatenation words[i] + words[j] is a palindrome. Return all such pairs as a list of [i, j], sorted in ascending order. The input is JSON {words}.

Input: JSON {words}.

Output: Array — the list of index pairs, sorted ascending.

Examples

Input: {"words":["abcd","dcba","lls","s","sssll"]}
Output: [[0,1],[1,0],[2,4],[3,2]]
Explanation: Four concatenations are palindromes.

Input: {"words":["bat","tab","cat"]}
Output: [[0,1],[1,0]]
Explanation: 'battab' and 'tabbat'.

Input: {"words":["a",""]}
Output: [[0,1],[1,0]]
Explanation: An empty word pairs with a palindrome.

Constraints

• 1<=n<=5000
• 0<=|words[i]|<=300

Asked by