# 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:

```text
words[i] + words[j]
```

is a palindrome.

A palindrome reads the same forward and backward.

For example:

```text
"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

| Item | Meaning |
|---|---|
| Input | `words`, a list of unique strings |
| Output | List of index pairs `[i, j]` |
| Condition | `i != j` |
| Valid pair | `words[i] + words[j]` is a palindrome |

Function shape:

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

## Examples

Example 1:

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

Valid concatenations:

| Pair | Concatenation |
|---|---|
| `[0, 1]` | `"abcd" + "dcba" = "abcddcba"` |
| `[1, 0]` | `"dcba" + "abcd" = "dcbaabcd"` |
| `[3, 2]` | `"s" + "lls" = "slls"` |
| `[2, 4]` | `"lls" + "sssll" = "llssssll"` |

Example 2:

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

Valid concatenations:

```text
"bat" + "tab" = "battab"
"tab" + "bat" = "tabbat"
```

Example 3:

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

The empty string can pair with any palindrome word.

```text
"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.

```python
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:

```text
O(n^2 * k)
```

The number of word pairs can be very large.

## Key Insight

For two words `a` and `b`, the concatenation:

```text
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:

```text
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.

```text
reverse(suffix) + prefix + suffix
```

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

This gives a pair:

```text
[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.

```text
prefix + suffix + reverse(prefix)
```

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

This gives a pair:

```text
[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:

```text
word -> index
```

Then for each word:

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

```text
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:

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

Dictionary:

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

For word `"abcd"` at index `0`.

One split is:

```text
prefix = "abcd"
suffix = ""
```

The suffix is a palindrome.

We need:

```text
reverse(prefix) = "dcba"
```

That exists at index `1`, so add:

```text
[0, 1]
```

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

```text
[1, 0]
```

For word `"lls"` at index `2`.

Split:

```text
prefix = "ll"
suffix = "s"
```

The suffix `"s"` is a palindrome.

We need:

```text
reverse(prefix) = "ll"
```

No such word exists.

Another split:

```text
prefix = "l"
suffix = "ls"
```

No useful match.

Another split:

```text
prefix = ""
suffix = "lls"
```

No useful match.

Now for word `"s"` at index `3`.

Split:

```text
prefix = "s"
suffix = ""
```

The suffix is a palindrome.

We need:

```text
reverse(prefix) = "s"
```

But that is the same word, so skip.

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

```text
prefix = "ll"
suffix = "s"
```

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

Instead, for `"lls"` split:

```text
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:

```text
"s" + "lls" = "slls"
```

So add:

```text
[3, 2]
```

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

```text
prefix = "sss"
suffix = "ll"
```

The prefix `"sss"` is a palindrome.

We need:

```text
reverse(suffix) = "ll"
```

No match.

Another split:

```text
prefix = "ss"
suffix = "sll"
```

The prefix `"ss"` is a palindrome.

We need:

```text
reverse(suffix) = "lls"
```

That exists at index `2`, so add:

```text
[2, 4]
```

because:

```text
"lls" + "sssll" = "llssssll"
```

## Correctness

Take any valid pair `(i, j)`.

Let:

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

and suppose:

```text
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:

| Symbol | Meaning |
|---|---|
| `n` | Number of words |
| `k` | Maximum word length |

The implementation below tries every split of every word.

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * k^2)` | `k` splits, each with substring and palindrome checks |
| Space | `O(n * k)` | Dictionary stores all words |

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

## Implementation

```python
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:

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

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

The palindrome helper is:

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

For every word, try all split positions:

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

At each split:

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

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

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

If that word exists, add:

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

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

```python
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

```python
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:

| Test | Why |
|---|---|
| Main sample | Checks multiple split types |
| `["bat","tab","cat"]` | Direct reverse words |
| `["a",""]` | Empty string case |
| `["abc","cba","xy"]` | Simple reverse pair |
| `["","aba","xyz"]` | Empty string with palindrome word |
| Mixed short words | Checks prefix and suffix cases |