Description
Given a list of unique words, return all pairs of indices (i, j) where words[i] + words[j] forms a palindrome.
Examples
Input:
words = ["abcd","dcba","lls","s","sssll"]Output:
[[0,1],[1,0],[3,2],[2,4]]Explanation:
These pairs form palindromes when concatenated.
Input:
words = ["race","car","ab","ba",""]Output:
[[2,3],[3,2],[0,4],[1,4],[4,0],[4,1]]Explanation:
Valid pairs: 'ab'+'ba'='abba' (palindrome) and 'ba'+'ab'='baab' (palindrome). The empty string combined with any palindrome also works, but 'race' is not a palindrome. Two valid pairs exist at indices [0,1] and [1,0].
Input:
words = ["abc","cba","a","aa"]Output:
[[0,1],[1,0],[2,3]]Explanation:
Valid palindrome pairs: 'abc'+'cba'='abccba', 'cba'+'abc'='cbaabc', and 'a'+'aa'='aaa'. Also 'aa'+'a'='aaa' is valid. The four pairs are at indices [0,1], [1,0], [2,3], and [3,2].
Constraints
- •
1 ≤ words.length ≤ 5000 - •
0 ≤ words[i].length ≤ 300