948. Palindrome Pairs (Trie Approach)

Given a list of distinct words, count the number of ordered pairs (i, j) with i != j such that the concatenation words[i] + words[j] is a palindrome. The input is a JSON array of words.

Input: A JSON array of words.

Output: Integer — the number of palindrome pairs.

Examples

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

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

Input: ["a",""]
Output: 2
Explanation: Both concatenations are palindromes.

Constraints

• 1<=words<=5000
• words are distinct

Asked by