Palindrome pairs: word pairs that join into a palindrome

Given a list of distinct words, return every pair of indices (i, j) with i != j such that words[i] + words[j] is a palindrome. Checking every pair is too slow for long lists.

Interface

Unless you agree on a different interface with the interviewer, assume:

• palindrome_pairs(words: list[str]) -> list[list[int]] — any order.

Example

palindrome_pairs(["abc", "cba", "b", "cb", "a"])
->  [[0, 1], [1, 0], [2, 3], [3, 0]]
    # "abccba", "cbaabc", "bcb", "cbabc"
palindrome_pairs(["a", ""])  ->  [[0, 1], [1, 0]]    # the empty string pairs with any palindrome

Constraints

• Up to 5,000 words, each up to 300 lowercase letters; words are distinct and one may be empty.

Clarifying questions

• Can a word be empty?
• Are words distinct?
• Is (i, j) different from (j, i)? (Yes, both are listed when both work.)
• What is the maximum word length compared with the number of words?

What a strong answer covers

• Brute force is O(n² · L); the goal is about O(n · L²).
• A hash map from each reversed word to its index. For each word and each split into prefix and suffix: if the prefix is a palindrome and the reversed suffix is another word, that word goes first; if the suffix is a palindrome and the reversed prefix is another word, that word goes second.
• Avoiding duplicate pairs when a split is empty on either side, and never pairing a word with itself.
• A trie of reversed words as an alternative, with each node storing which words have a palindromic remainder below it.
• Edge cases: the empty string, single letters, words that are each other's reverse.

Follow-ups

• Return only the count of pairs.
• Words are added over time; answer pairs for each new word.
• Allow i == j, using the same word twice.