# Palindrome Pairs
**Difficulty:** HARD
[External](https://leetcode.com/problems/palindrome-pairs)
Canonical: https://scaleengineer.com/dsa/problems/palindrome-pairs
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Wix](https://scaleengineer.com/companies/wix), [Yandex](https://scaleengineer.com/companies/yandex)
---
## 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.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

**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.

# Approaches
## Brute Force
The most straightforward approach is to test every possible pair of words. We can use nested loops to iterate through all unique pairs of indices `(i, j)`. For each pair, we concatenate the two words `words[i]` and `words[j]`, and then check if the resulting string is a palindrome. If it is, we add the pair of indices to our result list.
**Time:** O(N^2 * K), where N is the number of words and K is the maximum length of a word. There are N * (N-1) pairs to check. For each pair, concatenation and palindrome check take O(K) time. · **Space:** O(K), where K is the maximum length of a word. This space is used to store the concatenated string. The space for the output list is not included in this analysis.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will likely time out on larger inputs.; The time complexity of O(N^2 * K) is too high given the constraints.
### Explanation
This method exhaustively checks every possible pair of distinct indices `(i, j)`. For each pair, it performs string concatenation, which takes time proportional to the lengths of the two strings. Then, it verifies if the new, longer string is a palindrome, which also takes time proportional to its length. While simple to implement, this approach is computationally expensive due to the number of pairs and the repeated work of concatenation and palindrome checking.

```java
class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        int n = words.length;
        if (n < 2) {
            return result;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                String combined = words[i] + words[j];
                if (isPalindrome(combined)) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        return result;
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   Initialize an empty list `result` to store the pairs of indices.
*   Iterate through the `words` array with an outer loop for index `i` from `0` to `n-1`.
*   Iterate through the `words` array with an inner loop for index `j` from `0` to `n-1`.
*   Inside the inner loop, check if `i` is not equal to `j`.
*   If `i != j`, concatenate `words[i]` and `words[j]` to form a new string `combinedWord`.
*   Check if `combinedWord` is a palindrome.
    *   A helper function `isPalindrome(s)` can be used. It checks for palindromes by comparing characters from the beginning and end of the string, moving inwards.
*   If `combinedWord` is a palindrome, add the pair `[i, j]` to the `result` list.
*   After the loops complete, return the `result` list.

## Using Hash Map
We can optimize the brute-force approach by avoiding the inner loop that iterates through all other words. Instead, for each word `w1`, we can deduce what its partner word `w2` must look like. If `w1 + w2` is a palindrome, `w2` must be related to the reverse of `w1`. We can pre-process the words into a `HashMap` for quick lookups.

There are three main scenarios for a pair `(w1, w2)`:
1.  `len(w1) == len(w2)`: `w2` must be the reverse of `w1`.
2.  `len(w1) > len(w2)`: `w1` must be of the form `P + S`, where `S` is the reverse of `w2` and `P` is a palindrome.
3.  `len(w1) < len(w2)`: `w2` must be of the form `S + P`, where `S` is the reverse of `w1` and `P` is a palindrome.

We can iterate through each word and all its possible splits into a prefix and a suffix. If one part is a palindrome, we look for the reverse of the other part in the map.
**Time:** O(N * K^2), where N is the number of words and K is the maximum length. For each of the N words, we iterate through K+1 split points. Inside the loop, substring creation, reversal, and palindrome checking can take up to O(K) time. · **Space:** O(N * K), for storing the words in the HashMap.
**Pros:** Significantly faster than the brute-force approach for N > K.; Avoids the O(N^2) pair iteration.
**Cons:** The time complexity of O(N * K^2) might still be too slow for the given constraints.; Requires careful handling of edge cases like empty strings and duplicate pairs.
### Explanation
This approach improves upon brute force by intelligently searching for the second word in a pair. By pre-populating a `HashMap` with all words and their indices, we can quickly check for the existence of a required word (e.g., the reverse of a suffix). The main logic involves iterating through each word and, for each word, iterating through all possible split points. This creates a prefix and a suffix. We check if either part is a palindrome. If the prefix is a palindrome, we need a word that is the reverse of the suffix to place *before* our current word. If the suffix is a palindrome, we need a word that is the reverse of the prefix to place *after* our current word.

```java
class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }

        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j <= word.length(); j++) {
                String prefix = word.substring(0, j);
                String suffix = word.substring(j);

                // Case 1: prefix is a palindrome, look for reversed suffix
                if (isPalindrome(prefix)) {
                    String reversedSuffix = new StringBuilder(suffix).reverse().toString();
                    if (map.containsKey(reversedSuffix) && map.get(reversedSuffix) != i) {
                        result.add(Arrays.asList(map.get(reversedSuffix), i));
                    }
                }

                // Case 2: suffix is a palindrome, look for reversed prefix
                // suffix.length() != 0 to avoid duplicates when word is a palindrome
                // (e.g. "aba", prefix="aba", suffix=""). This is handled by Case 1 when j=0.
                if (isPalindrome(suffix) && suffix.length() != 0) {
                    String reversedPrefix = new StringBuilder(prefix).reverse().toString();
                    if (map.containsKey(reversedPrefix) && map.get(reversedPrefix) != i) {
                        result.add(Arrays.asList(i, map.get(reversedPrefix)));
                    }
                }
            }
        }
        return result;
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   Create a `HashMap` to store each word and its index. This allows for O(1) average time lookups.
*   Handle the edge case of an empty string. If `""` exists in `words`, find its index. Then, iterate through all other words; if a word is a palindrome, it can form a pair with the empty string in both orders.
*   Iterate through each word `w` at index `i` in the `words` array.
*   For each word `w`, iterate through all possible split points `j` from `0` to `w.length()`.
*   Split `w` into `prefix = w.substring(0, j)` and `suffix = w.substring(j)`.
*   **Case 1:** Check if the `prefix` is a palindrome. If it is, reverse the `suffix` to get `reversedSuffix`. Look for `reversedSuffix` in the `HashMap`. If it exists at an index `k` different from `i`, then `(k, i)` is a palindrome pair (`words[k] + words[i]` forms a palindrome).
*   **Case 2:** Check if the `suffix` is a palindrome. If it is, reverse the `prefix` to get `reversedPrefix`. Look for `reversedPrefix` in the `HashMap`. If it exists at an index `k` different from `i`, then `(i, k)` is a palindrome pair. Note: When `j=0`, the prefix is empty, and this case becomes checking for the reverse of the whole word. To avoid duplicates when the suffix is empty (`j = w.length()`), we can add a condition `suffix.length() > 0` or use a `Set` for the results.

## Trie of Reversed Words
A Trie (prefix tree) can be used to optimize the search for the required reversed prefixes/suffixes. The core logic is similar to the HashMap approach, but the Trie structure allows us to efficiently search for all words that have a certain prefix.

We build a Trie containing all the words in their **reversed** form. Then, for each word `w` in the original list, we traverse the Trie. This traversal effectively compares `w` against the reversed forms of all other words. During the traversal, we can identify two types of palindrome pairs.
**Time:** O(N * K^2). For each of the N words, both building the Trie and searching involve a loop of length K, and inside it, a palindrome check that takes O(K). This results in O(K^2) work per word. · **Space:** O(N * K). The Trie can have up to N*K nodes in the worst case. The `palindromeSuffixes` lists can, in the worst case, lead to O(N^2) space, but on average, it's closer to O(N*K).
**Pros:** Structured approach that is a foundation for the most optimal solution.; Efficiently finds all candidates with a given prefix/suffix.
**Cons:** More complex to implement than the HashMap approach.; The naive implementation still has a time complexity of O(N * K^2) due to repeated palindrome checks on substrings.
### Explanation
This approach uses a Trie to structure the search. By inserting the reverse of each word, we can search for pairs more efficiently. When we search with a normal word `words[i]`, we are essentially matching its prefixes against the reversed suffixes of all other words in the dictionary.

1.  **`words[i]` + `words[j]` where `len(j) <= len(i)`**: `words[i]` must be of the form `P + S`, where `S = rev(words[j])` and `P` is a palindrome. While traversing the Trie with `words[i]`, if we hit a node that marks the end of a word `words[j]`, we have found a potential `S`. We then only need to check if the rest of `words[i]` (`P`) is a palindrome.

2.  **`words[i]` + `words[j]` where `len(j) > len(i)`**: `words[j]` must be of the form `rev(words[i]) + P`, where `P` is a palindrome. To find these, we augment our Trie nodes. When inserting `rev(words[j])`, we can pre-calculate and store at each node a list of all words that have a palindromic suffix starting from that node. Then, after traversing the Trie with `words[i]`, we can just look up this list at the final node.

```java
class Solution {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int wordEndIndex = -1;
        List<Integer> palindromeSuffixes = new ArrayList<>();
    }

    public List<List<Integer>> palindromePairs(String[] words) {
        TrieNode root = new TrieNode();
        for (int i = 0; i < words.length; i++) {
            addWord(root, words[i], i);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            search(words, i, root, result);
        }
        return result;
    }

    private void addWord(TrieNode root, String word, int index) {
        TrieNode curr = root;
        for (int j = word.length() - 1; j >= 0; j--) {
            if (isPalindrome(word, 0, j)) {
                curr.palindromeSuffixes.add(index);
            }
            int charIndex = word.charAt(j) - 'a';
            if (curr.children[charIndex] == null) {
                curr.children[charIndex] = new TrieNode();
            }
            curr = curr.children[charIndex];
        }
        curr.wordEndIndex = index;
        curr.palindromeSuffixes.add(index); // Empty string suffix is a palindrome
    }

    private void search(String[] words, int i, TrieNode root, List<List<Integer>> result) {
        String word = words[i];
        TrieNode curr = root;
        for (int j = 0; j < word.length(); j++) {
            if (curr.wordEndIndex != -1 && curr.wordEndIndex != i && isPalindrome(word, j, word.length() - 1)) {
                result.add(Arrays.asList(i, curr.wordEndIndex));
            }
            int charIndex = word.charAt(j) - 'a';
            if (curr.children[charIndex] == null) {
                return;
            }
            curr = curr.children[charIndex];
        }

        for (int k : curr.palindromeSuffixes) {
            if (k != i) {
                result.add(Arrays.asList(i, k));
            }
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
*   **Trie Node Structure**: Each node contains an array of children, an integer `wordEndIndex` (to store the index of a word ending at this node, initialized to -1), and a list `palindromeSuffixes`.
*   **Build Trie**: Iterate through each word `w` at index `i`. Insert the **reverse** of `w` into the Trie. During insertion, at each node, check if the remaining suffix of the reversed word is a palindrome. If it is, add the index `i` to the current node's `palindromeSuffixes` list. This list will help find pairs where the other word is longer.
*   **Search for Pairs**: Iterate through each word `w` at index `i` again.
    1.  Traverse the Trie with `w`. At each node `curr` in the traversal (after processing prefix `w[0...j-1]`):
        *   If `curr.wordEndIndex` is valid (not -1) and not `i`, it means we found a word `words[k]` whose reverse matches the current prefix of `w`. We then check if the remaining part of `w` (`w[j...end]`) is a palindrome. If so, `(i, k)` is a valid pair.
    2.  After traversing the entire word `w`, we are at a node `lastNode`.
        *   Check the `lastNode.palindromeSuffixes` list. For each index `k` in this list (where `k != i`), `(i, k)` is a valid pair. This handles cases where `words[k]` is longer than `words[i]`.

## Trie with Optimized Palindrome Checks
This is the most optimal approach and meets the strict time complexity requirement of `O(sum of words[i].length)`. It builds upon the previous Trie-based solution by eliminating the main bottleneck: the repeated, expensive `isPalindrome` checks on substrings. By pre-processing each word, we can make these checks instantaneous (O(1) time).
**Time:** O(N * K), where N is the number of words and K is the average word length. This is equivalent to O(S), where S is the total number of characters in all words. Each character is processed a constant number of times. · **Space:** O(N * K). The space is needed for the Trie and the pre-computed hash values for each word.
**Pros:** Achieves the optimal time complexity of O(N * K).; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Significantly more complex to implement due to the need for a robust hashing scheme (often requiring multiple hash functions to avoid collisions) or other advanced algorithms like Manacher's.; The constant factors are higher than in simpler approaches.
### Explanation
To achieve the `O(N * K)` runtime, we must optimize the `O(K)` palindrome check inside the `O(K)` loops of the Trie algorithm. The total work for each word of length K must be `O(K)`, not `O(K^2)`.

This can be achieved by using techniques like Manacher's algorithm or, more commonly in this context, string hashing. With string hashing, we can pre-calculate hash values for all prefixes of a string and its reverse. This allows us to find the hash of any substring in `O(1)` time. A substring is a palindrome if its hash is the same as the hash of its reverse. This check is also `O(1)`.

By replacing the `O(K)` `isPalindrome` function with an `O(1)` version (after an initial `O(K)` pre-processing step for each word), the complexity of both the `addWord` and `search` functions for a single word drops from `O(K^2)` to `O(K)`. Summing over all `N` words, the total time complexity becomes `O(N * K)`, which is equivalent to `O(S)`, the total number of characters in the input.

The Java code would be structurally identical to the previous Trie solution, with the crucial difference being the implementation of `isPalindrome`, which would now rely on pre-computed hash tables for `O(1)` lookups. Due to its complexity, the full hashing implementation is omitted, but it's the key to this optimal solution.
### Algorithm
*   The overall algorithm structure is identical to the previous Trie approach.
*   **Optimization**: The key change is to optimize the `isPalindrome` check. Instead of re-calculating it for every substring, which takes O(K) time, we can pre-process each word to answer any substring palindrome query in O(1) time.
*   **Pre-processing Method**: One common technique is to use **string hashing** (like the Rabin-Karp algorithm). For each word, we compute the polynomial rolling hash of its prefixes and the prefixes of its reversed version. With these pre-computed hashes, we can calculate the hash of any substring in O(1). A substring is a palindrome if its forward hash equals its reverse hash.
*   **Modified Trie Algorithm**:
    1.  **Pre-computation**: For each word, spend O(K) time to build its hash tables.
    2.  **Build Trie**: The `addWord` function is the same, but now the `isPalindrome` call inside the loop is an O(1) operation. The time to add a word becomes O(K).
    3.  **Search**: The `search` function is the same, but its `isPalindrome` call is also O(1). The time to search for a word's pairs becomes O(K).
*   The total time complexity is dominated by the pre-computation, building, and searching phases, each of which now takes O(N * K) time.

# Solutions
### CSharp

```csharp
using System.Collections.Generic ; using System.Linq ; public class Solution { public IList < IList < int >> PalindromePairs ( string [] words ) { var results = new List < IList < int >>(); var reverseDict = words . Select (( w , i ) => new { Word = w , Index = i }). ToDictionary ( w => new string ( w . Word . Reverse (). ToArray ()), w => w . Index ); for ( var i = 0 ; i < words . Length ; ++ i ) { var word = words [ i ]; for ( var j = 0 ; j <= word . Length ; ++ j ) { if ( j > 0 && IsPalindrome ( word , 0 , j - 1 )) { var suffix = word . Substring ( j ); int pairIndex ; if ( reverseDict . TryGetValue ( suffix , out pairIndex ) && i != pairIndex ) { results . Add ( new [] { pairIndex , i }); } } if ( IsPalindrome ( word , j , word . Length - 1 )) { var prefix = word . Substring ( 0 , j ); int pairIndex ; if ( reverseDict . TryGetValue ( prefix , out pairIndex ) && i != pairIndex ) { results . Add ( new [] { i , pairIndex }); } } } } return results ; } private bool IsPalindrome ( string word , int startIndex , int endIndex ) { var i = startIndex ; var j = endIndex ; while ( i < j ) { if ( word [ i ] != word [ j ]) return false ; ++ i ; -- j ; } return true ; } }
```

### Java

```java
class Solution {
private
  static final int BASE = 131;
private
  static final long[] MUL = new long[310];
private
  static final int MOD = (int)1 e9 + 7;
  static {
    MUL[0] = 1;
    for (int i = 1; i < MUL.length; ++i) {
      MUL[i] = (MUL[i - 1] * BASE) % MOD;
    }
  }
public
  List<List<Integer>> palindromePairs(String[] words) {
    int n = words.length;
    long[] prefix = new long[n];
    long[] suffix = new long[n];
    for (int i = 0; i < n; ++i) {
      String word = words[i];
      int m = word.length();
      for (int j = 0; j < m; ++j) {
        int t = word.charAt(j) - 'a' + 1;
        int s = word.charAt(m - j - 1) - 'a' + 1;
        prefix[i] = (prefix[i] * BASE) % MOD + t;
        suffix[i] = (suffix[i] * BASE) % MOD + s;
      }
    }
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (check(i, j, words[j].length(), words[i].length(), prefix, suffix)) {
          ans.add(Arrays.asList(i, j));
        }
        if (check(j, i, words[i].length(), words[j].length(), prefix, suffix)) {
          ans.add(Arrays.asList(j, i));
        }
      }
    }
    return ans;
  }
private
  boolean check(int i, int j, int n, int m, long[] prefix, long[] suffix) {
    long t = ((prefix[i] * MUL[n]) % MOD + prefix[j]) % MOD;
    long s = ((suffix[j] * MUL[m]) % MOD + suffix[i]) % MOD;
    return t == s;
  }
}

```

### Python

```python
class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]: d = {w: i for i, w in enumerate(words)} ans = [] for i, w in enumerate(words): for j in range(len(w) + 1): a, b = w[: j], w[j:] ra, rb = a[:: - 1], b[:: - 1] if ra in d and d[ra] != i and b == rb: ans . append([i, d[ra]]) if j and rb in d and d[rb] != i and a == ra: ans . append([d[rb], i]) return ans

```