class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for(int i = 0, n = words.length; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j)
                    continue;
                
                if(isPP(words[i], words[j]))
                    res.add(Arrays.asList(new Integer[]{i, j}));
            }
        }
        return res;
    }
    
    private boolean isPP(String w1, String w2){
        String w = w1 + w2;
        for(int i = 0, n = w.length(); i < n/2; i++)
            if(w.charAt(i) != w.charAt(n - 1 - i))
                return false;
        return true;
    }
}

class Solution {
    private static class TrieNode {
        // 保存下一个node的列表,长度为26,表示26个小写字母
        TrieNode[] next;
        // 在当前位置的word在 words中的index, 如果不是开始字符,那么值为-1
        // 在当前tree中是倒序储存, 所以是以开始字符为判断条件
        int index;
        // 保存满足以下条件的word的位置的list
        //  1.以到当前node为止的所有字符为后缀(注意, 在tree中是倒序储存)
        //  2.剩下的字符是回文
        List<Integer> list;

        TrieNode() {
            next = new TrieNode[26];
            index = -1;
            list = new ArrayList<>();
        }
    }

    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++)
            addWord(root, words[i], i);

        for (int i = 0; i < words.length; i++)
            search(words, i, root, res);

        return res;
    }

    // 对所有word做预处理,存入tree中
    private void addWord(TrieNode node, String word, int index) {
        for (int i = word.length() - 1; i >= 0; i--) {
            int j = word.charAt(i) - 'a';

            if (node.next[j] == null) 
                node.next[j] = new TrieNode();

            // 如果剩下的字符串是回文,那么存入list中
            if (isPalindrome(word, 0, i)) 
                node.list.add(index);

            node = node.next[j];
        }
        
        // word的第一个字符是回文,因为只有一个字符
        node.list.add(index);
        // 当前node是第一个字符,记录在words中的位置
        node.index = index;
    }

    private void search(String[] words, int i, TrieNode root, List<List<Integer>> res) {
        // 对words[i],从位置0开始正向遍历
        for (int j = 0; j < words[i].length(); j++) {
            // 如果trieTree中搜索已经完结(index>=0表示当前node是否个word的第一个字符),
            // 并且得到的node所代表的字符串不是word本身,
            // 并且word剩下的子字符串是回文
            if (root.index >= 0 && root.index != i && isPalindrome(words[i], j, words[i].length() - 1)) 
                res.add(Arrays.asList(i, root.index));

            // 如果tree中有对应的当前字符,继续
            // 否则结束计算
            root = root.next[words[i].charAt(j) - 'a'];
            if (root == null) return;
        }

        // 当word已经计算到最后一个字符, 而在tree中有对应的node的时候,
        // node的list中代表的字符串就都可以和当前字符串组成回文
        for (int j : root.list) {
            if (i == j) continue;
            res.add(Arrays.asList(i, j));
        }
    }

    // 判断字符串中从i到j位置的子字符串是否是回文
    private boolean isPalindrome(String word, int i, int j) {
        while (i < j) 
            if (word.charAt(i++) != word.charAt(j--)) return false;
        return true;
    }
}

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(words == null || words.length == 0)
            return res;

        //build the map save the key-val pairs: String - idx
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++)
            map.put(words[i], i);

        //special cases: "" can be combine with any palindrome string
        if(map.containsKey("")){
            int blankIdx = map.get("");
            for(int i = 0; i < words.length; i++){
                if(isPalindrome(words[i])){
                    if(i == blankIdx)
                        continue;
                    res.add(Arrays.asList(blankIdx, i));
                    res.add(Arrays.asList(i, blankIdx));
                }
            }
        }

        //find all string and reverse string pairs
        for(int i = 0; i < words.length; i++){
            String cur_r = reverseStr(words[i]);
            if(map.containsKey(cur_r)){
                int found = map.get(cur_r);
                if(found == i) continue;
                res.add(Arrays.asList(i, found));
            }
        }

        //find the pair s1, s2 that 
        //case1 : s1[0:cut] is palindrome and s1[cut+1:] = reverse(s2) => (s2, s1)
        //case2 : s1[cut+1:] is palindrome and s1[0:cut] = reverse(s2) => (s1, s2)
        for(int i = 0; i < words.length; i++){
            String cur = words[i];
            for(int cut = 1; cut < cur.length(); cut++){
                if(isPalindrome(cur.substring(0, cut))){
                    String cut_r = reverseStr(cur.substring(cut));
                    if(map.containsKey(cut_r)){
                        int found = map.get(cut_r);
                        if(found == i) continue;
                        res.add(Arrays.asList(found, i));
                    }
                }
                if(isPalindrome(cur.substring(cut))){
                    String cut_r = reverseStr(cur.substring(0, cut));
                    if(map.containsKey(cut_r)){
                        int found = map.get(cut_r);
                        if(found == i) continue;
                        res.add(Arrays.asList(i, found));
                    }
                }
            }
        }

        return res;
    }

    public String reverseStr(String str){
        StringBuilder sb= new StringBuilder(str);
        return sb.reverse().toString();
    }

    public boolean isPalindrome(String s){
        int i = 0, j = s.length() - 1;
        while(i <= j){
            if(s.charAt(i++) != s.charAt(j--))
                return false;
        }
        return true;
    }
}