题目：
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1: Given words = ["bat", "tab", "cat"] Return [[0, 1], [1, 0]] The palindromes are ["battab", "tabbat"]
Example 2: Given words = ["abcd", "dcba", "lls", "s", "sssll"] Return [[0, 1], [1, 0], [3, 2], [2, 4]] The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases.
分析：
class Solution { public List<List<Integer>> palindromePairs(String[] words) { //给定字符串集合，判断两个字符串组合是否能成为回文 //暴力解法可能超时 //思路：使用HashMap分别记录每个单词可以切分为回文的下表和切分字符串，因为如果单词的左边或者右边可以切分为回文 //只需要找到是否存在相同的匹配串，那么就可以组成一对回文串，例如：lls 切分 ll、s 如果列表中存在ll或者s就可以组成字符串 llsll、slls List<List<Integer>> list=new ArrayList<>(); HashMap<String,Integer> hm=new HashMap<>(); if(words.length<2||words==null) return list; //将单词和下表放入hm for(int i=0;i<words.length;i++){ hm.put(words[i],i); } //对每个单词进行切分处理 for(int i=0;i<words.length;i++){ for(int j=0;j<=words[i].length();j++){ //j<=words[i].length主要是为了防止["a",""]空单词的出现 String str1=words[i].substring(0,j); String str2=words[i].substring(j); //判断切分的两部分是否为回文 //左边 if(isPalindrome(str1)){ //判断是否存在另一半部分的逆序字符串 String str2Reverse=new StringBuilder(str2).reverse().toString(); if(hm.containsKey(str2Reverse)&&hm.get(str2Reverse)!=i){ //说明存在str2逆序，可以构成回文 List<Integer> subList=new ArrayList<>(); //左边的话，那么匹配的另外在其前面 subList.add(hm.get(str2Reverse)); subList.add(i); list.add(subList); } } //右边 if(isPalindrome(str2)){ String str1Reverse=new StringBuilder(str1).reverse().toString(); //防止重复判断"" 另str2.length()!=0，因为str1已经处理了""为空的情况 if(hm.containsKey(str1Reverse)&&hm.get(str1Reverse)!=i&&str2.length()!=0){ List<Integer> subList=new ArrayList<>(); //右边的话，那么匹配的另外在其后面 subList.add(i); subList.add(hm.get(str1Reverse)); list.add(subList); } } } } return list; } public boolean isPalindrome(String str){ int start=0; int end=str.length()-1; while(start<end){ if(str.charAt(start++)!=str.charAt(end--)){ return false; } } return true; } }