字典树写法：

class Solution {//使用字典树（也叫前缀树）来解决此问题//首先构建字典树，实现insert和search方法class Node{//表示字母在字典树中的索引int[] pos = new int[26];//flag表示当前字符串对应的words中的索引int flag;public Node(){flag = -1;}}//创建一棵字典树，trie.get(p)代表p处的结点List<Node> trie = new ArrayList<>();//str是要插入的字符串，index代表它在words中的索引public void insert(String str,int index){int len = str.length();//p代表当前所处的结点位置int p = 0;for(int i = 0; i < len; i++){//这里相当于把字母映射成了一个数字，可以把word想象成字母int word = str.charAt(i) - 'a';//默认都从根节点开始插入，根节点为空，先看下根节点的孩子结点中有没有word，//没有的话，就创建一个新的结点用来存wordif(trie.get(p).pos[word] == 0){//创建新结点trie.add(new Node());//这个新结点的pos[word]表示结点编号，即字典树的第n个结点,也是该结点在trie树中的索引trie.get(p).pos[word] = trie.size()-1;}//更新p结点（当前结点），将字母word所在结点位置赋给p（当前结点），下一轮循环会从当前结点继续寻找下一个字母p = trie.get(p).pos[word];}//插入完成之后,将str在words中的索引赋给flagtrie.get(p).flag = index;}//查找字典树中是否存在某一个字符串的反转public int search(String str, int left, int right){//待查字符串的长度int len = right - left + 1;int p = 0;//因为是查字符串的反转，所以从后往前遍历for(int i = right; i >= left; i--){//判断当前结点的孩子结点中是否存在字母str.charAt(i)int word = str.charAt(i) - 'a';if(trie.get(p).pos[word] == 0){//为0表示子结点中不存在该字母，返回-1return -1;}//存在即更新当前结点，并继续查询下一个字母p = trie.get(p).pos[word];}//查到了就返回字符串在words中的索引return trie.get(p).flag;}//判断字符串是否为回文串public boolean isPalindrome(String str, int left, int right){int len = right - left + 1;for(int i = 0; i < len/2; i++){if(str.charAt(left + i) != str.charAt(right - i))return false;}return true;}public List<List<Integer>> palindromePairs(String[] words) {//添加空的根结点trie.add(new Node());//把所有单词插入到字典树for(int i = 0; i < words.length; i++){insert(words[i],i);}//定义一个结果集合List<List<Integer>> ans = new ArrayList<>();for(int i = 0; i < words.length; i++){int len = words[i].length();for(int j = 0; j <= len; j++){//如果后缀为回文串if(isPalindrome(words[i],j,len-1)){//那么去字典树中查询该字符串前部分的反转int leftIndex = search(words[i],0,j-1);if(leftIndex != -1 && leftIndex != i){ans.add(Arrays.asList(i,leftIndex));}}//如果前缀为回文串if(j != 0 && isPalindrome(words[i],0,j-1)){//那么去字典树中查询该字符串后部分的反转int rightIndex = search(words[i],j,len-1);if(rightIndex != -1 && rightIndex != i){ans.add(Arrays.asList(rightIndex,i));}}}}return ans;}
}

哈希表的写法

class Solution {List<String> wordsRev = new ArrayList<String>();Map<String, Integer> indices = new HashMap<String, Integer>();public List<List<Integer>> palindromePairs(String[] words) {int n = words.length;for (String word: words) {wordsRev.add(new StringBuffer(word).reverse().toString());}for (int i = 0; i < n; ++i) {indices.put(wordsRev.get(i), i);}List<List<Integer>> ret = new ArrayList<List<Integer>>();for (int i = 0; i < n; i++) {String word = words[i];int m = words[i].length();if (m == 0) {continue;}for (int j = 0; j <= m; j++) {if (isPalindrome(word, j, m - 1)) {int leftId = findWord(word, 0, j - 1);if (leftId != -1 && leftId != i) {ret.add(Arrays.asList(i, leftId));}}if (j != 0 && isPalindrome(word, 0, j - 1)) {int rightId = findWord(word, j, m - 1);if (rightId != -1 && rightId != i) {ret.add(Arrays.asList(rightId, i));}}}}return ret;}public boolean isPalindrome(String s, int left, int right) {int len = right - left + 1;for (int i = 0; i < len / 2; i++) {if (s.charAt(left + i) != s.charAt(right - i)) {return false;}}return true;}public int findWord(String s, int left, int right) {return indices.getOrDefault(s.substring(left, right + 1), -1);}
}

class Solution {public List<List<Integer>> palindromePairs(String[] words) {Trie trie1 = new Trie();Trie trie2 = new Trie();int n = words.length;for (int i = 0; i < n; i++) {trie1.insert(words[i], i);StringBuffer tmp = new StringBuffer(words[i]);tmp.reverse();trie2.insert(tmp.toString(), i);}List<List<Integer>> ret = new ArrayList<List<Integer>>();for (int i = 0; i < n; i++) {int[][] rec = manacher(words[i]);int[] id1 = trie2.query(words[i]);words[i] = new StringBuffer(words[i]).reverse().toString();int[] id2 = trie1.query(words[i]);int m = words[i].length();int allId = id1[m];if (allId != -1 && allId != i) {ret.add(Arrays.asList(i, allId));}for (int j = 0; j < m; j++) {if (rec[j][0] != 0) {int leftId = id2[m - j - 1];if (leftId != -1 && leftId != i) {ret.add(Arrays.asList(leftId, i));}}if (rec[j][1] != 0) {int rightId = id1[j];if (rightId != -1 && rightId != i) {ret.add(Arrays.asList(i, rightId));}}}}return ret;}public int[][] manacher(String s) {int n = s.length();StringBuffer tmp = new StringBuffer("#");for (int i = 0; i < n; i++) {if (i > 0) {tmp.append('*');}tmp.append(s.charAt(i));}tmp.append('!');int m = n * 2;int[] len = new int[m];int[][] ret = new int[n][2];int p = 0, maxn = -1;for (int i = 1; i < m; i++) {len[i] = maxn >= i ? Math.min(len[2 * p - i], maxn - i) : 0;while (tmp.charAt(i - len[i] - 1) == tmp.charAt(i + len[i] + 1)) {len[i]++;}if (i + len[i] > maxn) {p = i;maxn = i + len[i];}if (i - len[i] == 1) {ret[(i + len[i]) / 2][0] = 1;}if (i + len[i] == m - 1) {ret[(i - len[i]) / 2][1] = 1;}}return ret;}
}class Trie {class Node {int[] ch = new int[26];int flag;public Node() {flag = -1;}}List<Node> tree = new ArrayList<Node>();public Trie() {tree.add(new Node());}public void insert(String s, int id) {int len = s.length(), add = 0;for (int i = 0; i < len; i++) {int x = s.charAt(i) - 'a';if (tree.get(add).ch[x] == 0) {tree.add(new Node());tree.get(add).ch[x] = tree.size() - 1;}add = tree.get(add).ch[x];}tree.get(add).flag = id;}public int[] query(String s) {int len = s.length(), add = 0;int[] ret = new int[len + 1];Arrays.fill(ret, -1);for (int i = 0; i < len; i++) {ret[i] = tree.get(add).flag;int x = s.charAt(i) - 'a';if (tree.get(add).ch[x] == 0) {return ret;}add = tree.get(add).ch[x];}ret[len] = tree.get(add).flag;return ret;}
}