Palindrome Pairs

Palindrome Pairs takes the "remember what you've seen in a hash map" trick and stretches it over strings. The challenge is not the lookup itself but figuring out what to look up — and that comes from splitting each word into two halves.

The slow way first

The obvious idea: try every ordered pair (i, j), glue the two words together, and check whether the result is a palindrome. With n words of length up to m, that is O(n² · m) — far too slow once the list grows.

The question to ask: while I am looking at one word, what partner would complete a palindrome — and can I find it instantly instead of scanning? A hash map of reversed words lets us answer that in O(1).

The idea: split the word, look up the reverse

For two words a and b, a + b is a palindrome exactly when we can split one of them so that one side is itself a palindrome and the reverse of the other side equals the partner word. So we pre-build a map rev of every reversed word to its index, then for each word try every split point.

The two cases per split: if the prefix is a palindrome and the suffix exists reversed in the map, the partner goes in front; if the suffix is a palindrome and the prefix exists, the partner goes behind. Guard against pairing a word with itself.

Walk through it

Step through the animation. First we build rev (each reversed word to its index). Then the pointer i scans the words. For "bat", the empty-prefix split finds "bat" in the map at index 1, giving the pair [1, 0]. For "tab", the same split finds "tab" at index 0, giving [0, 1]. "cat" matches nothing.

Pseudocode

build rev = { reverse(word): index } for every word
pairs = empty list
for each index i with word w:
    for every split point k from 0 to len(w):
        pre, suf = w[:k], w[k:]
        if pre is a palindrome and reverse(suf) i.e. suf is a key in rev and rev[suf] != i:
            add [rev[suf], i]                 # partner goes in front
        if k > 0 and suf is a palindrome and pre is a key in rev and rev[pre] != i:
            add [i, rev[pre]]                 # partner goes behind
return pairs

The Python solution

def palindrome_pairs(words):
    rev = {w[::-1]: i for i, w in enumerate(words)}
    pairs = []
    for i, w in enumerate(words):
        for k in range(len(w) + 1):
            pre, suf = w[:k], w[k:]
            if pre == pre[::-1] and suf in rev and rev[suf] != i:
                pairs.append([rev[suf], i])
            if k and suf == suf[::-1] and pre in rev and rev[pre] != i:
                pairs.append([i, rev[pre]])
    return pairs

• rev maps each reversed word to its index, so a lookup is O(1).
• For each word we try every split into pre (prefix) and suf (suffix), including the empty ones.
• Line 7 is the front case: if pre is a palindrome and the suffix already exists reversed in rev, that stored word goes in front to complete the palindrome.
• Line 9 is the back case: if suf is a palindrome and the prefix exists reversed, the stored word goes behind. The k guard (and the empty-prefix check on line 7) avoids counting the same pair twice.
• rev[...] != i stops a word from pairing with itself.

Complexity

We trade the n² factor for an m² one — a big win when there are many words but they are short. The map costs O(n · m) space, which is the standard "remember everything so lookups are instant" trade.

When this pattern shows up

Practice