Course4all

Palindrome Pairs

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trie.

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)(i, j) in the array. Construct the string words[i] + words[j] and check if it is a palindrome. This is O(N2⋅L)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 WiW_i, we want to find WjW_j such that WiWjW_i W_j is a palindrome. This happens if WiW_i can be split into S1S2S_1 S_2 where S1S_1 is a palindrome and S2S_2 is the reverse of WjW_j, OR if Wi=S1S2W_i = S_1 S_2 where S2S_2 is a palindrome and S1S_1 is the reverse of WjW_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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionConcatenated Words
Next Question →Shortest Unique Prefix