// Runtime: 44 ms, faster than 74.91% of Java online submissions for Palindrome Pairs.
// Memory Usage: 54 MB, less than 19.51% of Java online submissions for Palindrome Pairs.
class Solution {
    private char[][] w;
    TrieNode trie = new TrieNode();

    public List<List<Integer>> palindromePairs(String[] words) {
        w = new char[words.length][];
        for (int i = 0; i < words.length; i++) w[i] = words[i].toCharArray();

        for (int i = 0; i < w.length; i++) {
            TrieNode node = trie;
            for (int j = 0; j < w[i].length; j++) {
                if (isPali(i, j, w[i].length - 1)) node.words.add(i);
                node = node.getNext(w[i][j]);
            }
            node.words.add(i);
            node.endWord = i;
        }

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        for (int i = 0; i < w.length; i++) {
            TrieNode node = trie;
            for (int j = w[i].length - 1; j >= 0 && node != null; j--) {
                if (node.endWord != -1 && node.endWord != i && isPali(i, 0, j))
                    result.add(Arrays.asList(node.endWord, i));

                node = node.getNext(w[i][j]);
            }
            if (node == null) continue;

            for (int wordIndex: node.words)
                if (wordIndex != i) result.add(Arrays.asList(wordIndex, i));
        }

        return result;
    }

    private boolean isPali(int i, int l, int r) {
        while (l < r)
            if (w[i][l++] != w[i][r--]) return false;

        return true;
    }

    class TrieNode {
        public List<Integer> words = new ArrayList<>();
        public TrieNode[] next= new TrieNode[26];
        public int endWord = -1;

        public TrieNode getNext(char c) {
            TrieNode n = next[c - 'a'];
            if (n == null) {
                n = new TrieNode();
                next[c - 'a'] = n;
            }
            return n;
        }
    }
}