题目

题解：

class Solution {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 List<List<Integer>> palindromePairs(String[] words) {int n=words.length;List<List<Integer>> res=new ArrayList<List<Integer>>();Trie trie=new Trie();for(int i=0;i<n;i++){trie.insert(words[i],i);}for(int i=0;i<n;i++){int m=words[i].length();for(int j=0;j<=m;j++){if(isPalindrome(words[i],j,m-1)){int leftId=trie.search(words[i].substring(0,j));if(leftId!=-1 && leftId!=i){res.add(Arrays.asList(i,leftId));}}if (j!=0 && isPalindrome(words[i],0,j-1)){int rightId=trie.search(words[i].substring(j,m));if (rightId!=-1 && rightId!=i) {res.add(Arrays.asList(rightId,i));}}}}return res;}
}class TrieNode{int val;boolean isEnd;TrieNode[] ch=new TrieNode[26];TrieNode() {}
}class Trie{TrieNode root;Trie(){root=new TrieNode();}void insert(String str,int id){TrieNode cur=root;for(int i=str.length()-1;i>=0;i--){int c=str.charAt(i)-'a';if(cur.ch[c]==null){cur.ch[c]=new TrieNode();}cur=cur.ch[c];}cur.isEnd=true;cur.val=id;}int search(String str){TrieNode cur=root;for(int i=0;i<str.length();i++){int c=str.charAt(i)-'a';if(cur.ch[c]==null){return -1;}cur=cur.ch[c];}if(cur.isEnd==true){return cur.val;}else{return -1;}}
}