Abstract / Summary

Given a list of words, find all pairs where combining them in some order forms a palindrome.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 37% (600k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Function
• Hash Table
• String
• Trie

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a method palindromePairs that receives a list of strings and returns all index pairs (i, j) such that the concatenation words[i] + words[j] forms a palindrome. The algorithm builds a hash-based lookup for the input words, iterates over each word, examines every possible split position, and checks whether the two halves are palindromic. When a matching reversed counterpart exists in the lookup, the corresponding index pair is added to a result set, which is finally returned.

Construction of the hash lookup

all = defaultdict(list)
for i, w in enumerate(words):
    all[hash(w)].append(i)   # rely on short hashes to save memory

A dictionary named all maps the hash of each word to a list of its positions in the original array. By storing only the hash rather than the full string, the structure reduces memory consumption, especially when many words share the same hash value. The use of defaultdict(list) automatically creates a list for a new hash key, simplifying insertion.

Main iteration over words and split positions

result = set()
for i, w in enumerate(words):
    for split in range(len(w) + 1):
        one = w[:split]
        two = w[split:]

The outer loop processes each word together with its index i. The inner loop enumerates every possible division of the word into a left part one and a right part two, including the empty prefix and suffix. This exhaustive split enables the detection of palindromes formed by attaching another word either before or after the current word.

Palindrome detection for the left part

revone = one[::-1]
revtwo = two[::-1]
if one == revone:
    h = hash(revtwo)
    if h in all:
        for j in all[h]:
            if i != j:
                result.add((j, i))

When the left segment one is itself a palindrome (one == revone), the algorithm looks for a word whose hash matches the reversed right segment revtwo. If such a word exists, any index j retrieved from the lookup (excluding the current index) yields a valid pair where the matching word precedes the current word ((j, i)). This captures cases where the suffix of the current word can be mirrored by a preceding word.

Palindrome detection for the right part

if two == revtwo:
    h = hash(revone)
    if h in all:
        for j in all[h]:
            if i != j:
                result.add((i, j))

Symmetrically, when the right segment two is a palindrome, the algorithm searches for a word whose hash equals the reversed left segment revone. Each qualifying index j (different from i) produces a pair where the matching word follows the current word ((i, j)). This handles situations where the prefix of the current word can be complemented by a trailing word.

Result collection

return result

All discovered pairs are stored in a Python set, guaranteeing uniqueness without additional checks. The final set is returned directly, providing the caller with a collection of distinct index tuples that satisfy the palindrome condition.

Edge-case handling

The algorithm naturally accommodates several special inputs:

• An empty string appears as a valid word; its hash is stored and any palindrome word will match when the empty string is paired on either side, because the empty string is trivially a palindrome.
• Single-character words are treated as palindromes; the left or right segment may become empty, and the corresponding reversed segment will also be empty, allowing matches with identical or different single-character entries.
• Duplicate words generate multiple indices under the same hash key; the inner loops iterate over all stored indices, ensuring that each distinct position participates in pair formation while the i != j guard prevents self-pairing.
• Words that are already palindromes are examined both as left and right segments, enabling pairs where a palindrome can be concatenated with another word that is its reverse.

Performance-related choices

The code employs several techniques that improve runtime characteristics:

• Storing only the hash of each word reduces the size of the lookup table, which can lead to faster hash table operations and lower memory pressure.
• Using a set for result eliminates the need for explicit duplicate detection logic; insertion into a set is amortized constant time.
• The palindrome checks (one == revone and two == revtwo) are performed before any lookup, preventing unnecessary hash calculations and dictionary accesses when the segment is not a palindrome.
• The reversed strings revone and revtwo are computed once per split and reused for both the left-side and right-side checks, avoiding redundant slicing operations.
• By iterating over range(len(w) + 1), the algorithm includes the split at the very end of the word, which captures the scenario where the entire word is considered as the left segment and the right segment is empty, a case essential for matching with empty strings.

These design decisions collectively contribute to an implementation that balances memory usage with computational efficiency while covering the full spectrum of palindrome pair possibilities.

Imagine you have a big treasure chest full of word blocks. The goal is to pick two blocks and glue them together to make a special kind of word that reads exactly the same both forward and backward, like the word radar.

The code starts by taking every word block and giving it a little label called a hash. This label acts like a shortcut, making it much faster to look for matching pieces later. It stores all these labels in a tidy list so no time is wasted searching through the whole pile every single time.

Then, the code starts looking at every word, one by one. It chops each word into two tiny pieces at every possible spot. After splitting a word, it checks two things. It looks at the first piece to see if it is already a mirror image of itself. If it is, the code hunts through the labels for the mirror image of the second piece. If it finds that piece in the pile, it knows that gluing them together will make a perfect mirror word.

Next, it does the exact same thing for the second piece. It checks if the second half is a mirror of itself and looks for the mirror of the first half in the pile. Every time it finds a pair that works, it writes down the position of these two words so they can be turned into a shiny new mirror word later. It keeps doing this for every single word until it has checked every possible combination in the chest.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python								TS
	WalkCCC	C++	Java	Python
	leetcode.ca		Java	Python		C#					Go
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	chenyanzhe	C++
	everthis				JS
	fartem								Ruby
	fengvyi	C++
	gouthampradhan		Java
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	martianoff						Scala
	qiyuangong		Java
	ruoru							Rust
	suxrobGM					C#
	varunu28		Java
	vli02									C
	vthwang		Java
	wisdompeak			Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C#, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
fengvyi	C++
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
martianoff	Scala
qiyuangong	Java
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality