// Runtime: 54 ms, Your runtime beats 71.38 % of java submissions.
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++) {
            String word = words[i];
            //System.out.println("Searching for " + word);
            TrieNode node = trie;
            for (int j = word.length() - 1; j >= 0 && node != null; j--) {
                char c = word.charAt(j);
                TrieNode next = node.next.get(c);

                if (node.endWord != -1) {
                    //System.out.println("1st word ended " + j);
                    if (node.endWord != i && isPali(word, 0, j)) {
                        result.add(createResult(node.endWord, i));
                    }
                }
                node = next;
            }
            if (node != null) {
                //System.out.println("2nd word ended");
                for (Pos pos: node.positions) {
                    if (pos.wordIndex == i) continue;

                    String firstWord = words[pos.wordIndex];
                    if (isPali(firstWord, pos.offset, firstWord.length() - 1)) {
                         result.add(createResult(pos.wordIndex, i));
                    }
                }
            }
        }

        return result;
    }

    private boolean isPali(String s, int l, int r) {
        //System.out.println("isPali: " + s + " " + l + " " + r);
        while (l < r)
            if (s.charAt(l++) != s.charAt(r--)) return false;

        return true;
    }

    private List<Integer> createResult(int index1, int index2) {
        ArrayList<Integer> r = new ArrayList<>();
        r.add(index1);
        r.add(index2);
        return r;
    }

    class TrieNode {
        public List<Pos> positions;
        public Map<Character, TrieNode> next;
        public int endWord;

        public TrieNode() {
            next = new HashMap<Character, TrieNode>();
            positions = new ArrayList<Pos>();
            endWord = -1;
        }

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

        private void addInt(String s, int index, int wordIndex) {
            positions.add(new Pos(wordIndex, index));
            if (index >= s.length()) {
                this.endWord = wordIndex;
                return;
            }

            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;
        }
    }

    class Pos {
        public int wordIndex;
        public int offset;
        public Pos(int wordIndex, int offset) {
            this.wordIndex = wordIndex;
            this.offset = offset;
        }
    }
}