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.lengthi != jwords[i] + words[j], the concatenation of the two strings, is a palindrome.
Return an array of all the palindrome pairs of words.
You must write an algorithm with O(sum of words[i].length) runtime complexity.
Example 1
Input
words = ["abcd","dcba","lls","s","sssll"]Output
[[0,1],[1,0],[3,2],[2,4]]The palindromes are ["abcddcba", "dcbaabcd", "slls", "llssssll"].
Example 2
Input
words = ["bat","tab","cat"]Output
[[0,1],[1,0]]The palindromes are ["battab", "tabbat"].
Constraints
- 1 <= words.length <= 5000
- 0 <= words[i].length <= 300
- words[i] consists of lowercase English letters.