336. Palindrome Pairs

/**

 * 336. Palindrome Pairs

 * 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”]

 */

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/trie/PalindromePairs.java

This problem has a unique and very elegant approach. Hence, have included this question here.

Conceptually understanding the problem:

• Problem is asking for palindrome pairs between words
• The question involves string matching and traversal so trie data structure can be used here
• A palindrome between two words occurs when one string matches the reverse of other, so we can add the words into a trie in reverse order
• Once the trie has been built we can iterate through trie to find relevant matches

Cases in which a palindrome can occur:

1. Word matches trie exactly and thus a one-to-one palindrome match occurs
2. The trie node contains another and the given word being iterated forms a palindrome via the remaining characters
3. Word has been fully exhausted but trie has one or more palindromes left

Here is the algorithm:

1. First build the trie using the words in their reverse order
   1. At each node in the trie if the sub word forms a palindrome, record that in the trie node
2. For each word
   1. iterate the characters while traversing the trie.
      1. Handle the case where trie node contains a given word and the remaining characters in the word being iterated form a palindrome. This is the case 2 above.  
   2. if the last node in trie contains another word once the original word has been completely iterated over then an exact palindrome match occurred. This is case 1 above
   3. after the complete word has been processed, if the trie node contains on or more palindromes then they must be accounted

Here is the code:

void processPalindrome() {
    for (int i = 0; i < words.length; i++) {
        String word = words[i];
        Trie node = root;
        for (int j = 0; j < word.length(); j++) {
            if ((node.wordId != -1) && isPalindrome(word.substring(j))) {
                //word has a palindrome left after match : case 2
                List<Integer> item = new ArrayList<>();
                item.add(i);
                item.add(node.wordId);
                results.add(item);
            }
            Character ch = word.charAt(j);
            node = node.child.get(ch);
            if (node == null) break;
        }
        if (node == null) {
            continue;
        }
        if (node.wordId != -1 && node.wordId != i) {
            //word had an exact palindrome match : case 1
            List<Integer> item = new ArrayList<>();
            item.add(i);
            item.add(node.wordId);
            results.add(item);
        }
        for (Integer k : node.palindromes) {
            //tree has one or more palindromes left : case 3
            List<Integer> item = new ArrayList<>();
            item.add(i);
            item.add(k);
            results.add(item);
        }
    }
}
void buildTrie() {
    for (int i = 0; i < words.length; i++) {
        String word = words[i];
        //add items in reverse to trie so that while walking the tree you match in reverse
        //to identify palindrome
        word = new StringBuilder(word).reverse().toString();
        Trie node = root;
        for (int j = 0; j < word.length(); j++) {
            //identify that there is a remaining palindrome after this node
            if (isPalindrome(word.substring(j))) {
                node.palindromes.add(i);
            }
            Character ch = word.charAt(j);
            node = node.child.computeIfAbsent(ch, k -> new Trie());
        }
        node.wordId = i;
    }
}