Solution: Palindrome Pairs

Explore how to find and return all valid palindrome pairs from an array of unique strings by leveraging a Trie data structure. Understand the core palindrome pairing cases, how to build and traverse the Trie with reversed words, and implement an algorithm with a time complexity of O(n×k²). This lesson helps you grasp efficient string concatenation techniques and palindrome detection to solve complex coding interview problems.

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