How do you approach Palindrome Pairs?

For each word, consider splitting it into a left part and right part.

What is the time complexity of Palindrome Pairs?

Time complexity: O(n k^2) where k is the average word length. Space complexity: O(n k).

What are common mistakes on Palindrome Pairs?

Leaving out the end-of-word flag, so a lookup reports words that were never inserted. Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest. Not handling the empty string, which is a valid prefix of everything.

gitGood.dev

← Back to problems

Palindrome Pairs

HardAlgorithms

Description

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

A palindrome pair is a pair of integers (i, j) such that:

0 <= i, j < words.length
i != j
The concatenation of words[i] + words[j] is a palindrome.

Return an array of all the palindrome pairs of indices. You may return the answer in any order.

Example 1

Input: words = ["abcd","dcba","lls","s","sssll"]

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

Explanation: "abcddcba", "dcbaabcd", "llssssll", and "slls" are palindromes.

Example 2

Input: words = ["bat","tab","cat"]

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

Explanation: "battab" and "tabbat" are palindromes.

Example 3

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

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

Explanation: "a" and "a" are both palindromes (empty string concatenation).

Constraints

- 1 <= words.length <= 5000 - 0 <= words[i].length <= 300 - words[i] consists of lowercase English letters.

Palindrome Pairs: approach, complexity and pitfalls

A hard trie problem, graded against 6 test cases (3 of them hidden).

The pattern: Trie

A prefix tree for fast string lookup by shared prefix.

Reach for it when you see: Many words, repeated prefix queries, autocomplete, or word-search over a grid.

If you are stuck

Show the 3-step hint ladder

For each word, consider splitting it into a left part and right part.
If the left part is a palindrome and the reverse of the right part exists in the list, that forms a valid pair.
Use a hash map for O(1) word lookups. Don't forget to handle the empty string case.

The optimal approach

Show the approach: Hash Map with Splits

Store all words in a hash map with their indices. For each word, try every split point. If the left part is a palindrome and the reverse of the right part exists as another word, prepend that word. Similarly, if the right part is a palindrome and the reverse of the left part exists, append that word. Deduplicate the results.

Time: O(n * k^2) where k is the average word length
Space: O(n * k)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Trie mistakes

These apply to the pattern as a whole, not just this problem.

Leaving out the end-of-word flag, so a lookup reports words that were never inserted.
Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest.
Not handling the empty string, which is a valid prefix of everything.

← Back to problems

Palindrome Pairs

HardAlgorithms

Description

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

A palindrome pair is a pair of integers (i, j) such that:

0 <= i, j < words.length
i != j
The concatenation of words[i] + words[j] is a palindrome.

Return an array of all the palindrome pairs of indices. You may return the answer in any order.

Example 1

Input: words = ["abcd","dcba","lls","s","sssll"]

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

Explanation: "abcddcba", "dcbaabcd", "llssssll", and "slls" are palindromes.

Example 2

Input: words = ["bat","tab","cat"]

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

Explanation: "battab" and "tabbat" are palindromes.

Example 3

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

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

Explanation: "a" and "a" are both palindromes (empty string concatenation).

Constraints

- 1 <= words.length <= 5000 - 0 <= words[i].length <= 300 - words[i] consists of lowercase English letters.

Palindrome Pairs: approach, complexity and pitfalls

A hard trie problem, graded against 6 test cases (3 of them hidden).

The pattern: Trie

A prefix tree for fast string lookup by shared prefix.

Reach for it when you see: Many words, repeated prefix queries, autocomplete, or word-search over a grid.

If you are stuck

Show the 3-step hint ladder

For each word, consider splitting it into a left part and right part.
If the left part is a palindrome and the reverse of the right part exists in the list, that forms a valid pair.
Use a hash map for O(1) word lookups. Don't forget to handle the empty string case.

The optimal approach

Show the approach: Hash Map with Splits

Time: O(n * k^2) where k is the average word length
Space: O(n * k)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Trie mistakes

These apply to the pattern as a whole, not just this problem.

Leaving out the end-of-word flag, so a lookup reports words that were never inserted.
Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest.
Not handling the empty string, which is a valid prefix of everything.