Solution: Palindrome Pairs

Explore how to detect all palindrome pairs in an array of unique words using a Trie. Understand the core cases for palindrome formation and efficiently implement solutions with reversed word insertions and palindrome checks to achieve optimal performance.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

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$
...