LeetCode 336: Palindrome Pairs

Problem Restatement

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

Return all pairs of different indices (i, j) such that:

words[i] + words[j]

is a palindrome.

A palindrome reads the same forward and backward.

For example:

"abccba"
"racecar"
""

are palindromes.

The problem asks for all valid pairs, not only one pair. The words are unique, and LeetCode asks for an algorithm close to the total input size. The standard hash-map split solution is commonly accepted, though its exact bound depends on substring and palindrome-check costs in the language.

Input and Output

Function shape:

def palindromePairs(words: list[str]) -> list[list[int]]:
    ...

Examples

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]

Valid concatenations:

Example 2:

Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]

Valid concatenations:

"bat" + "tab" = "battab"
"tab" + "bat" = "tabbat"

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]

The empty string can pair with any palindrome word.

"a" + "" = "a"
"" + "a" = "a"

First Thought: Try Every Pair

The simplest method is to try every ordered pair (i, j).

For each pair:

1. Skip if i == j.
2. Concatenate words[i] + words[j].
3. Check whether the result is a palindrome.

class Solution:
    def palindromePairs(self, words: list[str]) -> list[list[int]]:
        def is_palindrome(s: str) -> bool:
            return s == s[::-1]

        ans = []

        for i in range(len(words)):
            for j in range(len(words)):
                if i == j:
                    continue

                if is_palindrome(words[i] + words[j]):
                    ans.append([i, j])

        return ans

This is correct, but too slow.

If there are n words and each word has length up to k, this takes about:

O(n^2 * k)

The number of word pairs can be very large.

Key Insight

For two words a and b, the concatenation:

a + b

is a palindrome only if the unmatched part of one word is the reverse of the other word.

Instead of trying every second word, split each word into two parts:

word = prefix + suffix

There are two useful cases.

Case 1:

If prefix is a palindrome, then we need another word equal to reverse(suffix) placed before the current word.

reverse(suffix) + prefix + suffix

Since prefix is already a palindrome, the outer parts match.

This gives a pair:

[index_of_reverse_suffix, current_index]

Case 2:

If suffix is a palindrome, then we need another word equal to reverse(prefix) placed after the current word.

prefix + suffix + reverse(prefix)

Since suffix is already a palindrome, the outer parts match.

This gives a pair:

[current_index, index_of_reverse_prefix]

We can find these needed reversed words in O(1) average time using a hash map.

Algorithm

Build a dictionary:

word -> index

Then for each word:

1. Try every split position from 0 to len(word).
2. Let:

prefix = word[:cut]
suffix = word[cut:]

3. If prefix is a palindrome:

   1. Look for suffix[::-1] in the dictionary.
   2. If found at another index, add [that_index, i].

4. If suffix is a palindrome:

   1. Look for prefix[::-1] in the dictionary.
   2. If found at another index, add [i, that_index].

There is one duplication issue.

When cut == len(word), the suffix is empty. If we also handle empty-prefix cases carelessly, some pairs can be added twice. A simple fix is to run the suffix case only when cut != len(word).

Walkthrough

Use:

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

Dictionary:

"abcd"  -> 0
"dcba"  -> 1
"lls"   -> 2
"s"     -> 3
"sssll" -> 4

For word "abcd" at index 0.

One split is:

prefix = "abcd"
suffix = ""

The suffix is a palindrome.

We need:

reverse(prefix) = "dcba"

That exists at index 1, so add:

[0, 1]

For word "dcba" at index 1, similarly we find "abcd" and add:

[1, 0]

For word "lls" at index 2.

Split:

prefix = "ll"
suffix = "s"

The suffix "s" is a palindrome.

We need:

reverse(prefix) = "ll"

No such word exists.

Another split:

prefix = "l"
suffix = "ls"

No useful match.

Another split:

prefix = ""
suffix = "lls"

No useful match.

Now for word "s" at index 3.

Split:

prefix = "s"
suffix = ""

The suffix is a palindrome.

We need:

reverse(prefix) = "s"

But that is the same word, so skip.

The useful pair comes from word "lls" with a different split:

prefix = "ll"
suffix = "s"

Since suffix is palindrome, if "ll" existed then it would work. But it does not.

Instead, for "lls" split:

prefix = "ll"
suffix = "s"

This alone does not use "s". The pair [3, 2] is found when prefix = "ll" is palindrome and reverse(suffix) = "s" exists.

Then:

"s" + "lls" = "slls"

So add:

[3, 2]

For word "sssll" at index 4, a split finds:

prefix = "sss"
suffix = "ll"

The prefix "sss" is a palindrome.

We need:

reverse(suffix) = "ll"

No match.

Another split:

prefix = "ss"
suffix = "sll"

The prefix "ss" is a palindrome.

We need:

reverse(suffix) = "lls"

That exists at index 2, so add:

[2, 4]

because:

"lls" + "sssll" = "llssssll"

Correctness

Take any valid pair (i, j).

Let:

A = words[i]
B = words[j]

and suppose:

A + B

is a palindrome.

There are two possibilities.

If A is shorter than or equal to B, then the start of the palindrome must match the end. That means all of A must match the reverse of a suffix of B. The remaining prefix of B must be a palindrome. So when the algorithm processes B, it will find a split where prefix is a palindrome and reverse(suffix) = A, adding [i, j].

If A is longer than B, then all of B must match the reverse of a prefix of A. The remaining suffix of A must be a palindrome. So when the algorithm processes A, it will find a split where suffix is a palindrome and reverse(prefix) = B, adding [i, j].

Thus every valid pair is found.

The algorithm only adds a pair in two cases:

1. A palindromic prefix is surrounded by a word and its reverse.
2. A palindromic suffix is surrounded by a word and its reverse.

In both cases, the concatenation is guaranteed to read the same forward and backward.

The algorithm also checks that the two indices are different, so it never pairs a word with itself.

Therefore, it returns exactly all valid palindrome pairs.

Complexity

Let:

The implementation below tries every split of every word.

Each split may slice and reverse strings of length up to k.

A trie-based approach can reduce lookup structure differently, but the split-plus-hash-map method is shorter and easier to implement correctly.

Implementation

class Solution:
    def palindromePairs(self, words: list[str]) -> list[list[int]]:
        index = {word: i for i, word in enumerate(words)}
        ans = []

        def is_palindrome(s: str) -> bool:
            return s == s[::-1]

        for i, word in enumerate(words):
            for cut in range(len(word) + 1):
                prefix = word[:cut]
                suffix = word[cut:]

                if is_palindrome(prefix):
                    needed = suffix[::-1]

                    if needed in index and index[needed] != i:
                        ans.append([index[needed], i])

                if cut != len(word) and is_palindrome(suffix):
                    needed = prefix[::-1]

                    if needed in index and index[needed] != i:
                        ans.append([i, index[needed]])

        return ans

Code Explanation

Build the lookup table:

index = {word: i for i, word in enumerate(words)}

This lets us ask quickly whether a needed reversed word exists.

The palindrome helper is:

def is_palindrome(s: str) -> bool:
    return s == s[::-1]

For every word, try all split positions:

for cut in range(len(word) + 1):

At each split:

prefix = word[:cut]
suffix = word[cut:]

If the prefix is already a palindrome, we need the reverse of the suffix before the current word:

if is_palindrome(prefix):
    needed = suffix[::-1]

If that word exists, add:

ans.append([index[needed], i])

If the suffix is already a palindrome, we need the reverse of the prefix after the current word:

if cut != len(word) and is_palindrome(suffix):
    needed = prefix[::-1]

The cut != len(word) guard avoids adding duplicate pairs caused by the empty suffix.

Testing

def normalize(pairs):
    return sorted(map(tuple, pairs))

def run_tests():
    s = Solution()

    assert normalize(s.palindromePairs(
        ["abcd", "dcba", "lls", "s", "sssll"]
    )) == normalize([[0, 1], [1, 0], [3, 2], [2, 4]])

    assert normalize(s.palindromePairs(
        ["bat", "tab", "cat"]
    )) == normalize([[0, 1], [1, 0]])

    assert normalize(s.palindromePairs(
        ["a", ""]
    )) == normalize([[0, 1], [1, 0]])

    assert normalize(s.palindromePairs(
        ["abc", "cba", "xy"]
    )) == normalize([[0, 1], [1, 0]])

    assert normalize(s.palindromePairs(
        ["", "aba", "xyz"]
    )) == normalize([[0, 1], [1, 0]])

    assert normalize(s.palindromePairs(
        ["a", "b", "c", "ab", "ac", "aa"]
    )) == normalize([[0, 5], [5, 0], [1, 3], [2, 4]])

    print("all tests passed")

run_tests()

Test meaning: