336. Palindrome Pairs

Given a list ofuniquewords, find all pairs ofdistinctindices(i, j)in the given list, so that the concatenation of the two words, i.e.words[i] + words[j]is a palindrome.

Example 1:

Input: ["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: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 

Explanation: The palindromes are ["battab","tabbat"]

Thoughts:

1. Build the trie tree in a reverse order ( assume the answer will be "word" + "reverse suffix" in the trie tree). For each node N that consists of:

   1. the corresponding word index for current trie tree sequence representation from the root.

   2. next: children nodes

   3. cover list (list of word index in which the word contains the current trie suffix and MAY also contain palindrome on its left part itself.

2. Search each word w1 matching suffix by traversing down the trie tree. If there is a stop node before the leaf node of the Trie tree (TrieNode that represents a word w2 in reverse order and that word is not the wording being searched itself (w2 != w1)) and also the rest part of w1 (len(l2) > len(w1)) is also a palindrome, then an concatenation of w1 + w2 is an answer. Else if at the leaf node of the Trie, then adding in every index element in terminal nodes' cover list such that the concatenation of w2 + w1 are also answers. Thus, we find all the solutions.

Code: T: O(max(n * k^2, n^2) S:O(n^2 * k)

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>>res = new ArrayList<>();
        TrieNode root = new TrieNode();
        for(int i = 0; i < words.length; i++) addWords (root, words[i], i);
        for(int i = 0; i < words.length; i++) search (root, words[i], i, res);
        return res;
    }

    private void addWords(TrieNode root, String word, int index){
        for(int i = word.length() - 1; i >=0; --i){
            int pos = word.charAt(i) - 'a';
            if (isPalindrome(word, 0, i))
                root.cover.add(index);

            // checking & traversing down to the trie tree
            if(root.next[pos] == null) root.next[pos] = new TrieNode();
            root = root.next[pos];
        }
        root.index = index;
        root.cover.add(index);// since we have root node, in search when we go out of the for loop we
        // ends up in the terminate node, so we need to add itslef to the cover list
    }

    private void search(TrieNode root, String word, int index, List<List<Integer>> res){
        for(int i = 0; i < word.length(); i++){
            if(root.index >= 0 && root.index != index && isPalindrome(word, i, word.length() - 1)) res.add(Arrays.asList(index, root.index));
            int pos = word.charAt(i) - 'a';
            if(root.next[pos] == null) return;
            root = root.next[pos];
        }

        // add the cover list index 
        for(int i: root.cover){
            if(i != index)
                res.add(Arrays.asList(index, i));
        }
    }

    private boolean isPalindrome(String word, int i, int j){
        while(i < j){
            if(word.charAt(i++) != word.charAt(j--)) return false;
        }
        return true;
    }
}

class TrieNode{
    int index;
    TrieNode [] next;
    List<Integer> cover;

    TrieNode(){
        index = -1;
        next = new TrieNode [26];// consider small cases only
        cover = new ArrayList<>();
    }
}