LeetCode 336 - Palindrome Pairs
The problem gives us a list of unique strings called words. We must find every ordered pair of indices (i, j) such that: - i != j - concatenating words[i] + words[j] forms a palindrome A palindrome is a string that reads the same forward and backward.
Difficulty: 🔴 Hard
Topics: Array, Hash Table, String, Trie, Hash Function
Solution
Problem Understanding
The problem gives us a list of unique strings called words. We must find every ordered pair of indices (i, j) such that:
i != j- concatenating
words[i] + words[j]forms a palindrome
A palindrome is a string that reads the same forward and backward.
The important detail is that the pairs are ordered. If (0, 1) forms a palindrome, (1, 0) may or may not also form one, and both must be considered separately.
For example:
words = ["bat", "tab"]
"bat" + "tab" = "battab"which is a palindrome"tab" + "bat" = "tabbat"which is also a palindrome
So both [0,1] and [1,0] belong in the answer.
The constraints are large:
- Up to
5000words - Each word can have length up to
300
A brute force solution that checks every pair would require:
O(n^2 * k)
where:
nis the number of wordskis average word length
With 5000 words, this becomes too slow.
The problem explicitly asks for an algorithm with runtime proportional to the total length of all words, which strongly suggests we need a hash-based or trie-based optimization.
There are several important edge cases:
- Empty strings
- Single-character words
- Words that are already palindromes
- Reverse-word matches
- Cases where only part of a word participates in the palindrome structure
The uniqueness guarantee simplifies the implementation because we never have duplicate words mapped to different indices.
Approaches
Brute Force Approach
The most direct solution is to examine every ordered pair (i, j) where i != j.
For each pair:
- Concatenate
words[i] + words[j] - Check whether the result is a palindrome
A palindrome check takes O(k) time, where k is the combined string length.
Since there are O(n^2) pairs, total complexity becomes:
O(n^2 * k)
This approach is correct because it explicitly checks every possible pair. However, it is far too slow for n = 5000.
Optimal Approach
The key insight is that palindrome structure can be decomposed into prefixes and suffixes.
Suppose we split a word into:
word = prefix + suffix
If:
prefixis a palindrome- reverse(
suffix) exists elsewhere in the array
then:
reverse(suffix) + word
forms a palindrome.
Similarly, if:
suffixis a palindrome- reverse(
prefix) exists
then:
word + reverse(prefix)
forms a palindrome.
This allows us to avoid comparing every pair directly.
We store all words in a hash map:
word -> index
Then for each word, we try every possible split position and perform constant-time reverse lookups.
This dramatically reduces the search space.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n² × k) | O(1) | Checks every pair directly |
| Optimal | O(n × k²) | O(n × k) | Uses hash map and palindrome decomposition |
Here:
n= number of wordsk= maximum word length
Although O(n × k²) is not strictly linear in word length, it is accepted because k <= 300, making the solution practical.
Algorithm Walkthrough
- Create a hash map from each word to its index.
This allows constant-time lookup to determine whether a reversed substring exists elsewhere in the array. 2. Initialize an empty result list.
This will store all valid palindrome pairs. 3. For each word in the array, iterate through every possible split position.
If the word is:
word = prefix + suffix
then we consider every split from:
""
to
word
- Check whether the prefix is a palindrome.
If it is, then we only need the reverse of the suffix to appear elsewhere.
Example:
word = "lls"
split:
prefix = "ll"
suffix = "s"
prefix is palindrome
reverse(suffix) = "s"
Then:
"s" + "lls" = "slls"
which is a palindrome. 5. Check whether the suffix is a palindrome.
If it is, then the reverse of the prefix can be appended.
Example:
word = "sssll"
split:
prefix = "sss"
suffix = "ll"
suffix is palindrome
reverse(prefix) = "sss"
Then:
"llsss"
contributes to a valid pair. 6. Avoid pairing a word with itself.
Even if the reverse exists, the indices must differ. 7. Continue until all words and all split positions are processed. 8. Return the collected pairs.
Why it works
Every palindrome pair must have a symmetric structure around its center. By splitting each word into a prefix and suffix, we identify exactly the situations where the missing mirrored portion can be supplied by another word.
The algorithm is complete because every possible palindrome concatenation can be represented through one of these valid prefix/suffix decompositions.
Python Solution
from typing import List
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
def is_palindrome(s: str) -> bool:
return s == s[::-1]
word_to_index = {
word: i
for i, word in enumerate(words)
}
result = []
for index, word in enumerate(words):
length = len(word)
for split in range(length + 1):
prefix = word[:split]
suffix = word[split:]
# Case 1:
# reverse(suffix) + word
if is_palindrome(prefix):
reversed_suffix = suffix[::-1]
if (
reversed_suffix in word_to_index and
word_to_index[reversed_suffix] != index
):
result.append([
word_to_index[reversed_suffix],
index
])
# Case 2:
# word + reverse(prefix)
#
# split != length prevents duplicates
if split != length and is_palindrome(suffix):
reversed_prefix = prefix[::-1]
if (
reversed_prefix in word_to_index and
word_to_index[reversed_prefix] != index
):
result.append([
index,
word_to_index[reversed_prefix]
])
return result
The implementation begins by defining a helper function is_palindrome, which checks whether a string reads the same forward and backward.
Next, we construct word_to_index, a hash map that stores every word and its index. This gives constant-time lookup for reversed strings.
The outer loop processes each word individually. For every word, we examine every possible split position from 0 through len(word).
At each split:
prefix = word[:split]suffix = word[split:]
The algorithm then evaluates two cases.
The first case checks whether the prefix is a palindrome. If it is, then we search for the reverse of the suffix. If such a word exists, placing it before the current word forms a palindrome pair.
The second case checks whether the suffix is a palindrome. If it is, then the reverse of the prefix may be appended after the current word.
The condition:
split != length
prevents duplicate pairs from being added when the suffix is empty.
Finally, the accumulated list of pairs is returned.
Go Solution
package main
func palindromePairs(words []string) [][]int {
isPalindrome := func(s string) bool {
left := 0
right := len(s) - 1
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}
reverseString := func(s string) string {
bytes := []byte(s)
left := 0
right := len(bytes) - 1
for left < right {
bytes[left], bytes[right] = bytes[right], bytes[left]
left++
right--
}
return string(bytes)
}
wordToIndex := make(map[string]int)
for i, word := range words {
wordToIndex[word] = i
}
result := [][]int{}
for index, word := range words {
length := len(word)
for split := 0; split <= length; split++ {
prefix := word[:split]
suffix := word[split:]
// Case 1
if isPalindrome(prefix) {
reversedSuffix := reverseString(suffix)
if otherIndex, exists := wordToIndex[reversedSuffix]; exists && otherIndex != index {
result = append(result, []int{otherIndex, index})
}
}
// Case 2
if split != length && isPalindrome(suffix) {
reversedPrefix := reverseString(prefix)
if otherIndex, exists := wordToIndex[reversedPrefix]; exists && otherIndex != index {
result = append(result, []int{index, otherIndex})
}
}
}
}
return result
}
The Go implementation follows the same logic as the Python version, but there are a few language-specific differences.
Palindrome checking is implemented manually using two pointers because Go does not provide built-in slicing reversal like Python.
String reversal is handled by converting the string into a byte slice and swapping characters in place.
Go slices are lightweight views into arrays, so substring extraction with:
word[:split]
and
word[split:]
is efficient.
The result is stored as a slice of integer slices:
[][]int
which matches LeetCode's expected return type.
Worked Examples
Example 1
words = ["abcd","dcba","lls","s","sssll"]
Initial hash map:
| Word | Index |
|---|---|
| abcd | 0 |
| dcba | 1 |
| lls | 2 |
| s | 3 |
| sssll | 4 |
Processing "abcd"
| Split | Prefix | Suffix | Palindrome Check | Reverse Lookup | Pair |
|---|---|---|---|---|---|
| 0 | "" | abcd | prefix yes | dcba exists | [1,0] |
| 4 | abcd | "" | suffix yes | dcba exists | [0,1] |
Processing "lls"
| Split | Prefix | Suffix | Result |
|---|---|---|---|
| 2 | ll | s | prefix palindrome, reverse(s)="s" exists |
This gives:
[3,2]
because:
"s" + "lls" = "slls"
Processing "sssll"
| Split | Prefix | Suffix | Result |
|---|---|---|---|
| 2 | ss | sll | suffix palindrome after reverse lookup |
This produces:
[2,4]
Final answer:
[[0,1],[1,0],[3,2],[2,4]]
Example 2
words = ["bat","tab","cat"]
Hash map:
| Word | Index |
|---|---|
| bat | 0 |
| tab | 1 |
| cat | 2 |
Processing "bat"
At split 0:
| Prefix | Suffix | Reverse |
|---|---|---|
| "" | bat | tab |
"tab" exists, so:
[1,0]
At split 3:
| Prefix | Suffix | Reverse |
|---|---|---|
| bat | "" | tab |
This produces:
[0,1]
"cat" has no matching reverse structure.
Final answer:
[[0,1],[1,0]]
Example 3
words = ["a",""]
Hash map:
| Word | Index |
|---|---|
| a | 0 |
| "" | 1 |
Processing "a"
At split 0:
| Prefix | Suffix |
|---|---|
| "" | a |
Prefix is palindrome.
Reverse of suffix:
"a"
self-match, ignored.
At split 1:
| Prefix | Suffix |
|---|---|
| a | "" |
Suffix is palindrome.
Reverse of prefix:
"a"
self-match again.
But when processing the empty string:
"" + "a" = "a"
"a" + "" = "a"
Both are palindromes.
Final answer:
[[0,1],[1,0]]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n × k²) | Each word tries all splits and palindrome checks cost O(k) |
| Space | O(n × k) | Hash map stores all words |
For each word of length k, there are k + 1 split positions. At every split, palindrome checking and substring reversal may each cost O(k). Therefore total work per word is O(k²).
The hash map stores every word, requiring space proportional to the total input size.
Test Cases
from typing import List
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
def is_palindrome(s: str) -> bool:
return s == s[::-1]
word_to_index = {
word: i
for i, word in enumerate(words)
}
result = []
for index, word in enumerate(words):
for split in range(len(word) + 1):
prefix = word[:split]
suffix = word[split:]
if is_palindrome(prefix):
reversed_suffix = suffix[::-1]
if (
reversed_suffix in word_to_index and
word_to_index[reversed_suffix] != index
):
result.append([
word_to_index[reversed_suffix],
index
])
if split != len(word) and is_palindrome(suffix):
reversed_prefix = prefix[::-1]
if (
reversed_prefix in word_to_index and
word_to_index[reversed_prefix] != index
):
result.append([
index,
word_to_index[reversed_prefix]
])
return result
solution = Solution()
# Example 1
assert sorted(solution.palindromePairs(
["abcd","dcba","lls","s","sssll"]
)) == sorted([[0,1],[1,0],[3,2],[2,4]])
# Example 2
assert sorted(solution.palindromePairs(
["bat","tab","cat"]
)) == sorted([[0,1],[1,0]])
# Example 3, empty string handling
assert sorted(solution.palindromePairs(
["a",""]
)) == sorted([[0,1],[1,0]])
# Single palindrome word with empty string
assert sorted(solution.palindromePairs(
["aba",""]
)) == sorted([[0,1],[1,0]])
# No valid pairs
assert solution.palindromePairs(
["abc","def","ghi"]
) == []
# Reverse pairs
assert sorted(solution.palindromePairs(
["abc","cba"]
)) == sorted([[0,1],[1,0]])
# Multiple overlapping matches
assert sorted(solution.palindromePairs(
["a","aa","aaa"]
)) == sorted([
[0,1],[1,0],
[0,2],[2,0],
[1,2],[2,1]
])
# Empty string alone
assert solution.palindromePairs(
[""]
) == []
# Long palindrome structure
assert sorted(solution.palindromePairs(
["race","car","ecar","ace",""]
)) == sorted([
[0,2],[2,0]
])
Test Summary
| Test | Why |
|---|---|
["abcd","dcba","lls","s","sssll"] |
Validates mixed palindrome structures |
["bat","tab","cat"] |
Validates direct reverse matching |
["a",""] |
Tests empty string behavior |
["aba",""] |
Tests palindrome word with empty string |
["abc","def","ghi"] |
Ensures no false positives |
["abc","cba"] |
Tests exact reverse words |
["a","aa","aaa"] |
Tests overlapping palindrome relationships |
[""] |
Boundary case with only empty string |
["race","car","ecar","ace",""] |
Tests more complex substring interactions |
Edge Cases
Empty String
An empty string is tricky because concatenating it with any palindrome still produces a palindrome.
For example:
"" + "aba" = "aba"
"aba" + "" = "aba"
A naive implementation may forget to handle this special structure. The current algorithm handles it naturally through prefix and suffix splitting.
Self Matching
When reversing substrings, the reversed string may equal the current word itself.
For example:
word = "aba"
reverse(word) = "aba"
The problem requires i != j, so self-pairs are invalid. The implementation explicitly checks:
word_to_index[reversed_word] != index
to prevent incorrect matches.
Duplicate Pair Generation
When the suffix is empty, both palindrome conditions can produce the same pair.
Without careful handling, duplicate answers may appear.
The condition:
split != length
prevents the second case from running when the suffix is empty, eliminating duplicate generation cleanly.