LeetCode 336: Palindrome Pairs Solution in Python – A Step-by-Step Guide

What Is LeetCode 336: Palindrome Pairs?

In LeetCode 336: Palindrome Pairs, you’re given an array of unique strings words, and your task is to return all pairs of distinct indices (i, j) where words[i] + words[j] forms a palindrome. For example, with words = ["abcd","dcba","lls","s","sssll"], pairs include [0,1] ("abcd" + "dcba" = "abcddcba") and [1,0] ("dcba" + "abcd"). This problem tests your ability to optimize palindrome checks, connecting to concepts in LeetCode 125: Valid Palindrome.

Problem Statement

• Input: An array of unique strings words.
• Output: A list of index pairs [i, j] where words[i] + words[j] is a palindrome.
• Rules:
• i != j (distinct indices).
• Concatenation must form a palindrome (reads same forward and backward).
• Order of pairs doesn’t matter.

Constraints

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] contains only lowercase letters.

Examples

• Input: ["abcd","dcba","lls","s","sssll"]
• Output: [[0,1],[1,0],[3,2],[2,4]] (Pairs: "abcd"+"dcba", "dcba"+"abcd", "s"+"lls", "lls"+"sssll")
• Input: ["bat","tab","cat"]
• Output: [[0,1],[1,0]] (Pairs: "bat"+"tab", "tab"+"bat")
• Input: ["a",""]
• Output: [[0,1],[1,0]] (Pairs: "a"+"" = "a", ""+"a" = "a")

Understanding the Problem: Pairing Palindromes

To solve LeetCode 336: Palindrome Pairs in Python, we need to find all pairs of distinct indices where concatenating the words forms a palindrome. A naive approach—checking every pair—is O(n² * k), where n is the number of words and k is the max word length, too slow for 5000 words. Instead, we’ll use:

• Best Solution (Hash Map): O(n * k²) time, O(n) space—fast and scalable.
• Alternative Solution (Brute Force): O(n² * k) time, O(1) space—simple but inefficient.

Let’s start with the hash map solution, explained in a beginner-friendly way.

Best Solution: Hash Map Approach

Why This Is the Best Solution

The hash map approach is the top choice for LeetCode 336 because it’s efficient—O(n * k²) time, O(n) space—and uses a clever lookup to avoid checking all pairs. It stores reversed words and checks prefixes and suffixes for palindrome properties, reducing the problem to O(n) lookups with O(k²) palindrome checks. It’s like a word-matching detective—smart and quick!

How It Works

Think of this as a palindrome matcher:

• Step 1: Build Hash Map:
• Map each word’s reverse to its index.
• Step 2: Check Each Word:
• For word w at index i:
• Split w into prefix + suffix.
• If prefix is palindrome, check if suffix’s reverse is in map (w + rev(suffix)).
• If suffix is palindrome, check if prefix’s reverse is in map (rev(prefix) + w).
• Step 3: Collect Pairs:
• Add valid (i, j) pairs, ensuring i != j.
• Step 4: Why It Works:
• Covers all cases: full reverse, prefix/suffix palindromes.
• Hash map makes lookups O(1).

It’s like finding word soulmates with a quick scan!

Step-by-Step Example

Example: words = ["abcd","dcba"]

• Map: {"dcba":0, "abcd":1}
• Word "abcd" (i=0):
• "" (palindrome), rev("abcd")="dcba" in map → [0,1]
• "abcd" (not palindrome), skip
• Word "dcba" (i=1):
• "" (palindrome), rev("dcba")="abcd" in map → [1,0]
• Result: [[0,1], [1,0]]

Example: words = ["lls","s"]

• Map: {"sll":0, "s":1}
• "lls" (i=0):
• "l" (not palindrome), skip
• "ll" (palindrome), rev("s")="s" in map → [0,1]
• "s" (i=1):
• "" (palindrome), rev("s")="s" in map → skip (i=j)
• Result: [[0,1]]

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        # Build reverse map
        word_map = {word[::-1]: i for i, word in enumerate(words)}
        result = []

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

        # Check each word
        for i, word in enumerate(words):
            n = len(word)
            # Check all prefix/suffix splits
            for j in range(n + 1):
                prefix, suffix = word[:j], word[j:]
                # Prefix is palindrome, check suffix reverse
                if is_palindrome(prefix):
                    rev_suffix = suffix[::-1]
                    if rev_suffix in word_map and word_map[rev_suffix] != i:
                        result.append([word_map[rev_suffix], i])
                # Suffix is palindrome, check prefix reverse
                if j > 0 and is_palindrome(suffix):
                    rev_prefix = prefix[::-1]
                    if rev_prefix in word_map and word_map[rev_prefix] != i:
                        result.append([i, word_map[rev_prefix]])

        return result

• Line 3: Map reversed words to indices.
• Lines 6-7: Helper to check if a string is a palindrome.
• Lines 10-22: For each word:
• Split into prefix and suffix.
• If prefix is palindrome, check suffix’s reverse in map.
• If suffix is palindrome, check prefix’s reverse in map.
• Time Complexity: O(n * k²)—n words, O(k²) for palindrome checks.
• Space Complexity: O(n)—hash map.

This is like a palindrome-pairing wizard—fast and sharp!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute-force approach—O(n² * k) time, O(1) space—checks every pair of words by concatenating them and testing for palindromes. It’s the simplest way to understand the problem but too slow for 5000 words, making it a baseline for learning. It’s like pairing every word manually—thorough but tedious!

How It Works

Check all pairs:

• Step 1: Double loop over i, j (i ≠ j).
• Step 2: Concatenate words[i] + words[j].
• Step 3: Test if palindrome, add pair if true.

Step-by-Step Example

Example: words = ["abcd","dcba"]

• Pairs:
• [0,1]: "abcd"+"dcba" = "abcddcba" (palindrome) → [0,1]
• [1,0]: "dcba"+"abcd" = "dcbaabcd" (palindrome) → [1,0]
• Result: [[0,1], [1,0]]

Code for Brute Force Approach

Copy codeclass Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def is_palindrome(s):
            return s == s[::-1]

        result = []
        for i in range(len(words)):
            for j in range(len(words)):
                if i != j:
                    concat = words[i] + words[j]
                    if is_palindrome(concat):
                        result.append([i, j])

        return result

• Time Complexity: O(n² * k)—n² pairs, O(k) palindrome check.
• Space Complexity: O(1)—just result list.

It’s a pair-checking slogger—basic but slow!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n * k²) time, O(n) space, scalable.
• Cons: Requires prefix/suffix logic.
• Brute Force (Alternative):
• Pros: O(n² * k) time, O(1) space, straightforward.
• Cons: Too slow for large n.

Hash map wins for performance.

Additional Examples and Edge Cases

• [""]: [] (no distinct pairs).
• ["a","a"]: [[0,1], [1,0]].
• ["ab","ba"]: [[0,1], [1,0]].

Both handle these, but hash map is faster.

Complexity Breakdown

• Hash Map: Time O(n * k²), Space O(n).
• Brute Force: Time O(n² * k), Space O(1).

Hash map is the clear choice.

Key Takeaways

• Hash Map: Lookup magic—efficient!
• Brute Force: Pair all—simple!
• Python: Strings and dicts shine—see [Python Basics](/python/basics).
• Palindromes: Symmetry unlocks pairs.

Final Thoughts: Pair the Palindromes

LeetCode 336: Palindrome Pairs in Python is a string-matching masterpiece. The hash map solution offers speed and elegance, while brute force provides a tangible baseline. Want more string challenges? Try LeetCode 125: Valid Palindrome or LeetCode 647: Palindromic Substrings. Ready to pair? Head to Solve LeetCode 336 on LeetCode and match those words today!