LeetCode: Palindrome Pairs

/**
Given a list of unique words, find all pairs of distinct indices (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"]

Ref:https://leetcode.com/problems/palindrome-pairs/discuss/79195/O(n-*-k2)-java-solution-with-Trie-structure
*/
class TrieNode {
int index;
Map<Character, TrieNode> map;
List<Integer> list;
TrieNode() {
index = -1;
map = new HashMap<>();
list = new ArrayList<>();
}
}
public class PalindromePairs{
TrieNode root;
 
    private void insert(String s, int index) {
        TrieNode cur = root;
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
//the word itself can be palindrome and can form a pair with an empty string
            if (isPalindrome(s, 0, i)) cur.list.add(index);
            if (!cur.map.containsKey(c)) cur.map.put(c, new TrieNode());
            cur = cur.map.get(c);
        }
        cur.index = index;
        cur.list.add(index);
    }
 
    private void search(String s, int index, List<List<Integer>> res) {
        TrieNode cur = root;
        for (int i = 0; i < s.length(); i++) {
            if (cur.index != -1 && cur.index != index && isPalindrome(s, i, s.length() - 1)) {
                res.add(Arrays.asList(index, cur.index));
            }
            char c = s.charAt(i);
            if (!cur.map.containsKey(c)) return;
            cur = cur.map.get(c);
        }
        for (int i : cur.list) {
            if (i == index) continue;
            res.add(Arrays.asList(index, i));
        }
    }
 
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }
 
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<>();
        if (words == null || words.length == 0) return res;
     
        root = new TrieNode();
     
        for (int i = 0; i < words.length; i++) {
            insert(words[i], i);
        }
     
        for (int i = 0; i < words.length; i++) {
            search(words[i], i, res);
        }
     
        return res;
    }
}