> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Palindrome Pairs Python Solution with Tests

> Tested Python solution for LeetCode 336 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 336, Hard. Topics: Array, Hash Table, String, Trie. [View on LeetCode](https://leetcode.com/problems/palindrome-pairs/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 336   # by problem number
lcpy gen -s palindrome_pairs   # by problem name
```

## Problem

You are given a **0-indexed** array of **unique** strings `words`.

A **palindrome pair** is a pair of integers `(i, j)` such that:

* `0 <= i, j < words.length`,
* `i != j`, and
* `words[i] + words[j]` (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of `words`.

You must write an algorithm with `O(sum of words[i].length)` runtime complexity.

### Examples

```
Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]
```

```
Input: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
```

```
Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]
```

### Constraints

* 1 \<= words.length \<= 5000
* 0 \<= words\[i].length \<= 300
* `words[i]` consists of lowercase English letters.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/palindrome_pairs/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/palindrome_pairs/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Hash map of reversed word -> index. For each word, split into prefix/suffix
    # at every cut. If prefix palindrome, reversed suffix in map -> pair (j, i).
    # If suffix palindrome, reversed prefix in map -> pair (i, j). Handle empty string.
    # Time: O(sum of words[i].length)
    # Space: O(sum of words[i].length)
    def palindrome_pairs(self, words: list[str]) -> list[list[int]]:
        word_to_index = {word: i for i, word in enumerate(words)}
        result: list[list[int]] = []

        for i, word in enumerate(words):
            for j in range(len(word) + 1):
                prefix = word[:j]
                suffix = word[j:]
                # Reverse of prefix matches another word and current suffix is palindrome
                # -> that word + word forms palindrome: pair (other, i)
                if prefix == prefix[::-1]:
                    back = suffix[::-1]
                    if back != word and back in word_to_index:
                        result.append([word_to_index[back], i])
                # Reverse of suffix matches another word (not the full word itself) and
                # current prefix is palindrome -> word + that word: pair (i, other)
                if j != len(word) and suffix == suffix[::-1]:
                    front = prefix[::-1]
                    if front != word and front in word_to_index:
                        result.append([i, word_to_index[front]])

        return result
```

## Complexity

| Time                       | Space                      |
| -------------------------- | -------------------------- |
| O(sum of words\[i].length) | O(sum of words\[i].length) |

## Tags

[Grind](/catalog/grind).