Palindrome Pairs

Problem

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.

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","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]]

Constraints:

1 <= words.length <= 5000
0 <= words[i].length <= 300
words[i] consists of lower-case English letters.

Solution

/**
 * @param {string[]} words
 * @return {number[][]}
 */
var palindromePairs = function(words) {
    // construct and insert words into trie
    const trie = new Trie();
    for (let i = 0; i < words.length; i++) {
        const w = words[i];
        trie.insert(w, i);
    }

    // find palindrome pairs
    const res = [];
    for (let i = 0; i < words.length; i++) {
        const w = words[i];
        trie.palindromePairs(w, i, res);
    }
    return res;
};

class Node {
    constructor() {
        this.end = false;
        this.index = -1; // words[index] ending at his node
        this.indices = []; // indices i where the rest of words[i] is a palindrome
        this.children = {};
    }
}

class Trie {
    constructor() {
        this.root = new Node();
    }

    // insert words[index] = word into trie
    insert(word, index) {
        let r = this.root;
        for (let i = 0; i < word.length; i++) {
            const c = word[i];

            // rest of word is palindrome
            if (this.isPalindrome(word, i, word.length - 1)) {
                r.indices.push(index);
            }

            if (!(c in r.children)) {
                r.children[c] = new Node();
            }
            r = r.children[c];
        }
        r.end = true;
        r.index = index; // words[index] = word ends here
        r.indices.push(index); // word[word.length:] (ie. empty string) is palindrome
    }

    // finds all i such that words[i] + word is a palindrome
    palindromePairs(word, index, res) {
        let r = this.root;
        for (let i = word.length - 1; i >= 0; i--) {
            const c = word[i];

            // bullet 2 of explanation
            if (r.end && this.isPalindrome(word, 0, i)) {
                res.push([r.index, index]);
            }

            if (!(c in r.children)) {
                return;
            }
            r = r.children[c];
        }

        // bullet 1 of explanation
        for (const i of r.indices) {
            if (i !== index) { // only include distinct index pairs
                res.push([i, index]);
            }
        }
    }

    // test if word[lo:hi + 1] is a palindrome
    isPalindrome(word, lo, hi) {
        while (lo < hi) {
            if (word[lo++] !== word[hi--]) {
                return false;
            }
        }
        return true;
    }
}

We will use a trie to implement our solution. In our trie, we add two additional fields index and indices at each node. Where index is the index of the word in words that ends at the current node; and indices is an array that contains indices of words in words such that the rest (ie. suffix) of each word starting from the current node is a palindrome. Using these fields, there are two cases to consider for finding all indices i such that words[i] + word is a palindrome:

For word.length <= words[i].length, if the reverse of word is a prefix of words[i], and the rest of words[i] is a palindrome, then words[i] + word is a palindrome. In other words, reverse(word) == words[i][0:word.length] and words[i][word.length:words[i].length] is a palindrome implies words[i] + word is a palindrome.
- For example, if word = "ab" and words[i] = "baa", then it fits this case, and so "word[i] + word = "baa" + "ab" = baaab" is a palindrome.
For word.length > words[i].length, if the prefix of the reversed word is equal to words[i] and the rest of word is a palindrome, then words[i] + word is a palindrome. In other words, words[i] == reverse(word)[0:words[i].length] and reverse(word)[words[i].length:word.length] is a palindrome implies words[i] + word is a palindrome.
- For example, if word = "baa" and words[i] = "aa", then it fits this case, and so "word[i] + word = "aa" + "baa" = aabaa" is a palindrome.

Thus, we check these two cases as we traverse down our trie with every word in words.

Problem​

Solution​

Problem

Solution