class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        TrieNode trie = new TrieNode();
        for (int i = 0; i < words.length; i++) trie.add(words[i], i);

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

        for (int i = 0; i < words.length; i++) {
            List<FindResult> finds = trie.findBackwards(words[i]);
            for (FindResult find: finds) {
                if (find.wordIndex == i) continue;
                ArrayList<Integer> r = new ArrayList<>();
                r.add(find.wordIndex);
                r.add(i);
                result.add(r);
            }
        }

        return result;
    }

    class TrieNode {
        int wordIndex;
        Map<Character, TrieNode> next;

        public TrieNode() {
            next = new HashMap<Character, TrieNode>();
            wordIndex = -1;
        }

        public void add(String s, int wordIndex) {
            addInt(s, 0, wordIndex);
        }

        private void addInt(String s, int index, int wordIndex) {
            if (index >= s.length()) {
                this.wordIndex = wordIndex;
            }
            else {
                char c = s.charAt(index);
                TrieNode n = getOrAdd(c);
                n.addInt(s, index +  1, wordIndex);
            }
        }

        private TrieNode getOrAdd(char c) {
            TrieNode n = next.get(c);
            if (n == null) {
                n = new TrieNode();
                next.put(c, n);
            }
            return n;
        }

        public List<FindResult> findBackwards(String s) {
            List<FindResult> res = new ArrayList<>();
            TrieNode node = this;
            for (int i = s.length()-1; i>=0; i--){
                char c = s.charAt(i);
                node = node.next.get(c);
                if (node == null) break;
                if (node.wordIndex != -1) res.add(new FindResult(node.wordIndex, i));
            }
            return res;
        }
    }

    class FindResult {
        public int strIndex;
        public int wordIndex;
        public FindResult(int wordIndex, int strIndex){
            this.wordIndex = wordIndex;
            this.strIndex = strIndex;
        }
    }
}