All problems

Palindrome Pairs

Hard · trie

You are given a list words of different lowercase words. A word may be empty (the empty word joins to nothing).

Find every pair of positions [i, j] with i != j such that writing words[i] followed by words[j] gives a palindrome, a string that reads the same forwards and backwards. The order matters: [i, j] and [j, i] are two different pairs, and each may or may not qualify.

Return all qualifying pairs, sorted by i and then by j. Return an empty list if there are none.

Examples

Example 1

Input: words = ["code", "edoc", "da", "d"]

Output: [[0, 1], [1, 0], [2, 3]]

"code" + "edoc" = "codeedoc" is a palindrome, and so is "edoc" + "code" = "edoccode". "da" + "d" = "dad" is one too, but "d" + "da" = "dda" is not.

Example 2

Input: words = ["a", ""]

Output: [[0, 1], [1, 0]]

The empty word adds nothing, so "a" + "" = "a" and "" + "a" = "a" are both palindromes.

Constraints