Palindrome Pairs

Master this topic with zero to advance depth.

Palindrome Pairs

Given a list of unique words, return all pairs of distinct indices (i, j) such that the concatenation of the two words words[i] + words[j] is a palindrome.

Visual Representation

Words: ["abcd", "dcba", "lls", "s", "sssll"]

Pairs:
1. "abcd" + "dcba" = "abcddcba" (Palindrome)
2. "dcba" + "abcd" = "dcbaabcd" (Palindrome)
3. "s" + "lls" = "slls" (Palindrome)
4. "sssll" + "lls" = "ssslllls" (Wait, no...)
Wait: "lls" + "s" = "llss" (No)
Actual: "sssll" + "lls" -> "ssslllls" NO.
Let's check "lls" reverse is "sll".
If we pick i="sssll", j="lls", words[i]+words[j] = "ssslllls" Fails.
Correct for "lls": s + lls = slls (Correct).

Hard

Examples

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

Approach 1

Level I: Brute Force (Check all pairs)

Intuition

Iterate through every pair of indices $(i, j)$ in the array. Construct the string words[i] + words[j] and check if it is a palindrome. This is $O(N^2 \cdot L)$ , which is too slow for large inputs.

⏱ O(N^2 * L)💾 O(1)

java

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i == j) continue;
                if (isPal(words[i] + words[j])) res.add(Arrays.asList(i, j));
            }
        }
        return res;
    }
    boolean isPal(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
}

Approach 2

Level III: Trie (Suffix-to-Prefix matching)

Intuition

For a word $W_i$ , we want to find $W_j$ such that $W_i W_j$ is a palindrome. This happens if $W_i$ can be split into $S_1 S_2$ where $S_1$ is a palindrome and $S_2$ is the reverse of $W_j$ , OR if $W_i = S_1 S_2$ where $S_2$ is a palindrome and $S_1$ is the reverse of $W_j$ . A Trie storing words in reverse allows us to efficiently find these matches.

⏱ O(N * L^2).💾 O(N * L).

java

import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; int index = -1; List<Integer> list = new ArrayList<>(); }
    public List<List<Integer>> palindromePairs(String[] words) {
        Node root = new Node();
        for (int i = 0; i < words.length; i++) {
            String rev = new StringBuilder(words[i]).reverse().toString();
            Node curr = root;
            for (int j = 0; j < rev.length(); j++) {
                if (isPal(rev, j, rev.length() - 1)) curr.list.add(i);
                int c = rev.charAt(j) - 'a';
                if (curr.children[c] == null) curr.children[c] = new Node();
                curr = curr.children[c];
            }
            curr.index = i;
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            Node curr = root;
            for (int j = 0; j < words[i].length(); j++) {
                if (curr.index != -1 && curr.index != i && isPal(words[i], j, words[i].length() - 1)) res.add(Arrays.asList(i, curr.index));
                curr = curr.children[words[i].charAt(j) - 'a'];
                if (curr == null) break;
            }
            if (curr != null) {
                if (curr.index != -1 && curr.index != i) res.add(Arrays.asList(i, curr.index));
                for (int j : curr.list) res.add(Arrays.asList(i, j));
            }
        }
        return res;
    }
    private boolean isPal(String s, int i, int j) {
        while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
        return true;
    }
}

← Previous QuestionConcatenated Words

Next Question →Shortest Unique Prefix

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.