264. Palindrome Pairs (Count)

Given a list of unique words, return the number of ordered pairs (i, j) with i != j such that the concatenation words[i] + words[j] is a palindrome. Input: a JSON array of strings.

Input: JSON array of strings.

Output: Integer — count of palindrome pairs.

Examples

Input: ["abcd","dcba","lls","s","sssll"]
Output: 4
Explanation: Pairs like (0,1),(1,0),(3,2),(2,4).

Input: ["bat","tab","cat"]
Output: 2
Explanation: (0,1) and (1,0).

Input: ["a",""]
Output: 2
Explanation: 'a'+''='a' and ''+'a'='a'.

Constraints

• 1<=words.length<=300
• 0<=words[i].length<=100

Asked by