Problem statement

You are given an array of unique strings words (a word may be the empty string).

A palindrome pair is a pair of indices [i, j] with i != j such that words[i] + words[j] (the two words concatenated) is a palindrome.

Return all palindrome pairs, sorted by i and then by j.

Example 1

Input: words = ["code","edoc","x","","kayak"]
Output: [[0,1],[1,0],[2,3],[3,2],[3,4],[4,3]]
Explanation: `codeedoc` and `edoccode` are palindromes, and the empty word pairs with every palindromic word on either side.

Example 2

Input: words = ["kai","iak","ak"]
Output: [[0,1],[0,2],[1,0]]
Explanation: `kaiiak`, `kaiak` and `iakkai`.

Example 3

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

Constraints

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lowercase English letters
• All the strings in words are unique

Hints for Palindrome Pairs

1. Hint 1

   Trying every pair is O(n^2 · L). Instead, for each word, ask which partner would complete it to a palindrome.

2. Hint 2

   Split w into prefix + suffix. If prefix is a palindrome, then reverse(suffix) + w is a palindrome — so look up reverse(suffix) in a hash map of words.

3. Hint 3

   Symmetrically, if suffix is a palindrome, w + reverse(prefix) is a palindrome. Skip the second check for the split where suffix is empty, or pairs of equal-length words are found twice.

How to solve Palindrome Pairs

If a + b is a palindrome, the longer word splits into a palindromic piece and a piece that is the reverse of the shorter word. So for each word and each of its L + 1 split points, two hash lookups find every partner.

Approach

1. Map every word to its index.
2. For each word w at index i and each cut 0 <= k <= |w|, let pre = w[0..k) and suf = w[k..).
3. If pre is a palindrome and reverse(suf) is a word at index j != i, record [j, i] (reverse(suf) + pre + suf is a palindrome).
4. If k != |w|, suf is a palindrome and reverse(pre) is a word at index j != i, record [i, j] (pre + suf + reverse(pre) is a palindrome).
5. Sort the recorded pairs.

Why it works

Take a palindrome pair a + b. If |a| >= |b|, then a starts with reverse(b) and the rest of a is a palindrome — that is the second rule applied to a with k = |b|. If |a| <= |b|, then b ends with reverse(a) and the start of b is a palindrome — the first rule applied to b. When |a| == |b| both rules would fire; excluding k = |w| in the second rule keeps exactly one of them, so every pair is produced once.

Complexity

• Time — O(n · L^2)
• Space — O(n · L)

Pitfalls

• The empty word pairs with every palindromic word in both orders.
• A word must not pair with itself (j != i), even when it is a palindrome.
• Without the k != |w| guard, pairs of equal-length words such as code/edoc appear twice.

Reference solution

Python

from typing import List

def palindromePairs(words: List[str]) -> List[List[int]]:
    index = {w: i for i, w in enumerate(words)}
    res = []
    for i, w in enumerate(words):
        n = len(w)
        for k in range(n + 1):
            pre, suf = w[:k], w[k:]
            if pre == pre[::-1]:
                j = index.get(suf[::-1])
                if j is not None and j != i:
                    res.append([j, i])
            if k != n and suf == suf[::-1]:
                j = index.get(pre[::-1])
                if j is not None and j != i:
                    res.append([i, j])
    res.sort()
    return res

Java

static boolean ppIsPal(String w, int lo, int hi) {
    hi--;
    while (lo < hi) {
        if (w.charAt(lo) != w.charAt(hi)) return false;
        lo++;
        hi--;
    }
    return true;
}

public static int[][] palindromePairs(String[] words) {
    Map<String, Integer> index = new HashMap<>();
    for (int q = 0; q < words.length; q++) index.put(words[q], q);
    List<int[]> res = new ArrayList<>();
    for (int i = 0; i < words.length; i++) {
        String w = words[i];
        int n = w.length();
        for (int k = 0; k <= n; k++) {
            if (ppIsPal(w, 0, k)) {
                Integer j = index.get(new StringBuilder(w.substring(k)).reverse().toString());
                if (j != null && j != i) res.add(new int[]{j, i});
            }
            if (k != n && ppIsPal(w, k, n)) {
                Integer j = index.get(new StringBuilder(w.substring(0, k)).reverse().toString());
                if (j != null && j != i) res.add(new int[]{i, j});
            }
        }
    }
    res.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
    return res.toArray(new int[0][]);
}

C++

static bool ppIsPal(const string& w, int lo, int hi) {
    hi--;
    while (lo < hi) {
        if (w[lo] != w[hi]) return false;
        lo++;
        hi--;
    }
    return true;
}

vector<vector<int>> palindromePairs(vector<string>& words) {
    unordered_map<string, int> index;
    for (int q = 0; q < (int)words.size(); q++) index[words[q]] = q;
    vector<vector<int>> res;
    for (int i = 0; i < (int)words.size(); i++) {
        const string& w = words[i];
        int n = w.size();
        for (int k = 0; k <= n; k++) {
            if (ppIsPal(w, 0, k)) {
                string back(w.rbegin(), w.rbegin() + (n - k));
                auto it = index.find(back);
                if (it != index.end() && it->second != i) res.push_back({it->second, i});
            }
            if (k != n && ppIsPal(w, k, n)) {
                string back(w.rend() - k, w.rend());
                auto it = index.find(back);
                if (it != index.end() && it->second != i) res.push_back({i, it->second});
            }
        }
    }
    sort(res.begin(), res.end());
    return res;
}

JavaScript

var palindromePairs = function(words) {
    var index = new Map();
    for (var q = 0; q < words.length; q++) index.set(words[q], q);
    var isPal = function(w, lo, hi) {
        hi--;
        while (lo < hi) {
            if (w[lo] !== w[hi]) return false;
            lo++;
            hi--;
        }
        return true;
    };
    var rev = function(w, lo, hi) {
        var r = "";
        for (var t = hi - 1; t >= lo; t--) r += w[t];
        return r;
    };
    var res = [];
    for (var i = 0; i < words.length; i++) {
        var w = words[i], n = w.length;
        for (var k = 0; k <= n; k++) {
            if (isPal(w, 0, k)) {
                var j = index.get(rev(w, k, n));
                if (j !== undefined && j !== i) res.push([j, i]);
            }
            if (k !== n && isPal(w, k, n)) {
                var j2 = index.get(rev(w, 0, k));
                if (j2 !== undefined && j2 !== i) res.push([i, j2]);
            }
        }
    }
    res.sort(function(a, b) { return a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]; });
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard