MANG Problem #38: Palindrome Pairs (Hard)

1. Problem Statement

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

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

2. Approach: Reversed Word Trie

A brute force $O(N^2 \times K)$ solution checking every pair is too slow.

If word1 + word2 is a palindrome, then word1 must be the reverse of word2 (or parts of them must be palindromes themselves).

1. Build a Trie: Insert the reverse of every word into a Trie. Store the word's index at the leaf.
2. Search: For every word in the list, search it in the Trie.
   • Case 1: word matches a reverse word exactly (e.g., "abc" and "cba").
   • Case 2: word is longer. We reach a leaf in the Trie. The rest of word must be a palindrome (e.g., "abcdc" and "ba").
   • Case 3: word is shorter. The Trie path continues. The remaining path in the Trie must form a palindrome (e.g., "ab" and "cdcba").

To optimize Case 3, every TrieNode stores a list of indices representing words whose remaining suffix forms a palindrome.

3. Java Implementation

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    int wordIndex = -1;
    List<Integer> palindromePrefixes = new ArrayList<>();
}

public List<List<Integer>> palindromePairs(String[] words) {
    TrieNode root = new TrieNode();
    // 1. Build Trie with reversed words
    for (int i = 0; i < words.length; i++) {
        String rev = new StringBuilder(words[i]).reverse().toString();
        TrieNode curr = root;
        for (int j = 0; j < rev.length(); j++) {
            if (isPalindrome(rev, j, rev.length() - 1)) {
                curr.palindromePrefixes.add(i);
            }
            int idx = rev.charAt(j) - 'a';
            if (curr.next[idx] == null) curr.next[idx] = new TrieNode();
            curr = curr.next[idx];
        }
        curr.wordIndex = i;
        curr.palindromePrefixes.add(i);
    }

    List<List<Integer>> res = new ArrayList<>();
    // 2. Search each word
    for (int i = 0; i < words.length; i++) {
        TrieNode curr = root;
        String w = words[i];
        for (int j = 0; j < w.length(); j++) {
            if (curr.wordIndex != -1 && curr.wordIndex != i && isPalindrome(w, j, w.length() - 1)) {
                res.add(Arrays.asList(i, curr.wordIndex));
            }
            curr = curr.next[w.charAt(j) - 'a'];
            if (curr == null) break;
        }
        if (curr != null && curr.palindromePrefixes.size() > 0) {
            for (int pIdx : curr.palindromePrefixes) {
                if (i != pIdx) res.add(Arrays.asList(i, pIdx));
            }
        }
    }
    return res;
}

private boolean isPalindrome(String s, int left, int right) {
    while (left < right) if (s.charAt(left++) != s.charAt(right--)) return false;
    return true;
}

4. 5-Minute "Video-Style" Walkthrough

1. The Reverse Trick: If I have "bat" and I want to form a palindrome, I need something ending in "tab". By storing the reverse of words ("tab" becomes "bat"), finding a match becomes a standard prefix search!
2. The Partial Match: If I have "batman", I can match with "tab" ONLY if the remaining part "man" is a palindrome (it's not).
3. The Fast Lookup: The palindromePrefixes list in the Trie node is the ultimate optimization. It pre-calculates which words have palindromic remainders, saving us from checking it during the search phase.