Palindrome Pairs

Statement

You are given a 0-indexed array of unique strings called words.

A palindrome pair is defined as a pair of indexes (i, j) where both i and j are within the valid range of the list of words (that is, $0 \leq$ i, j $<$ words.length), and i is not equal to j. The key condition is that when the word at index i is concatenated with the word at index j (forming words[i] + words[j]), the resulting string must be a palindrome.

Your task is to return all valid palindrome pairs as a list of index pairs.

Additionally, your solution must have a time complexity of $O(\text{sum of}$ words.length$)$.

Constraints:

• $1 \leq$ words.length $\leq 1000$

• $0 \leq$ words[i].length $\leq 300$

• words[i] consists of lowercase English letters

• All strings in words unique

Examples