回文对

示例 1:

输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]] 
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2:

输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]] 
解释: 可拼接成的回文串为 ["battab","tabbat"]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

word1 = “accbc”     word2 = "ca"

word1 = “ad”     word2 = "bbada"

class Solution {
    public static class Node{
        // 中间结点值均为-1，结尾结点值为该字符串的下标索引
        int index;
        Node[] next;
        public Node(){
            this.index = -1;
            this.next = new Node[26];
        }
    }
    // 插入逆置后的单词
    public void insertWord(String str, int index){
        Node node = root;
        for(int i = str.length() - 1; i >= 0; i--){
            char cur = str.charAt(i);
            if(node.next[cur - 'a'] == null){
                node.next[cur - 'a'] = new Node();
            }
            node = node.next[cur - 'a'];
            if(i == 0){
                node.index = index;
            }
        }
    }
    // 将回文对存入result中
    public void find(String perfix,int index, List<List<Integer>> result){
        List<Integer> list = new ArrayList<>();
        Node node = root;
        for(int i = 0; i < perfix.length(); i++){
            char cur = perfix.charAt(i);
            if(node.next[cur - 'a'] == null){
                return;
            }
            node = node.next[cur - 'a'];
            // word1比word2长的情况
            if(i != perfix.length() - 1 && node.index != -1){
                if(isPalin(perfix, i + 1, perfix.length() - 1)){
                    List<Integer> temp = new ArrayList<>(2);
                    temp.add(index);
                    temp.add(node.index);
                    result.add(temp);
                }
            }
        }
        // word1比word2短或等于的情况
        dfs(node, result, index);
    }
    public void dfs(Node node, List<List<Integer>> result, int index){
        if(node.index != -1 && node.index != index){
            if(isPalin(words[node.index], 0, words[node.index].length() - words[index].length() - 1)){
                List<Integer> temp = new ArrayList<>(2);
                temp.add(index);
                temp.add(node.index);
                result.add(temp);
            }
        }
        for(Node temp : node.next){
            if(temp == null){
                continue;
            }
            dfs(temp, result, index);
        }
    }
    public boolean isPalin(String str, int left, int right){
        while(left < right){
            if(str.charAt(left++) != str.charAt(right--)){
                return false;
            }
        }
        return true;
    }

    Node root = new Node();
    String[] words = null;
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        this.words = words; 
        for(int i = 0; i < words.length; i++){
            insertWord(words[i], i);
        }
        int nullIndex = -1;
        for(int i = 0; i < words.length; i++){
            if(words[i].length() == 0){
                nullIndex = i;
                continue;
            }
            find(words[i], i, result);
        }
        if(nullIndex != -1){
            for(int j = 0; j < words.length; j++){
                if(j == nullIndex){
                    continue;
                }
                if(isPalin(words[j], 0, words[j].length() - 1)){
                    List<Integer> temp1 = new ArrayList<>(2);
                    List<Integer> temp2 = new ArrayList<>(2);
                    temp1.add(nullIndex);
                    temp1.add(j);
                    temp2.add(j);
                    temp2.add(nullIndex);
                    result.add(temp1);
                    result.add(temp2);
                }
            }
        }
        return result;

    }
}