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:

解题思路

首先想到的是暴力组合，分别检验所有组合是否为回文，该方法提交后超时，暴力代码如下：

//Time Limit Exceededpublic class Solution {
         public List
     
      
       > palindromePairs(String[] words) {        List
       
        
         > indices = new ArrayList<>();        for (int i = 0; i < words.length; i++) {            for (int j = 0; j < words.length; j++) {                if (j == i) {                    continue;                } else {                    String temp = words[i] + words[j];                    if (isPalindrome(temp)) {                        List
         
           list = new ArrayList<>();                        list.add(i);                        list.add(j);                        indices.add(list);                    }                }            }        }        return indices;    }    private boolean isPalindrome(String word) {        for (int i = 0, j = word.length() - 1; i < j; i++, j--) {            if (word.charAt(i) != word.charAt(j)) {                return false;            }        }        return true;    }}
         
        
       
      
     

于是想到另一种思路：

1. 对于空字符串，如果数组中有回文字符串，则将空字符串与回文字符串进行组合。
2. 对于非空字符串，将其进行拆分，如果其中一段为回文，并且数组中可以找到另一段的逆序字符串，则说明可以组合为回文。
   例如：”sssll” = “ss” + “sll”，而且数组中存在”lls”，因此组合”lls”和”sssll”。

注意：组合两个字符串时，需要注意顺序问题。如果字符串前半段为回文，则另一个字符串需要组合在前面；如果字符串后半段为回文，则另一个字符串需要组合在后面。

实现代码

//Runtime: 247 mspublic class Solution {
         public List
     
      
       > palindromePairs(String[] words) {        Map
       
         map = new HashMap<>();        for (int i = 0; i < words.length; i++) {            map.put(words[i], i);        }        List
        
         
          > indices = new ArrayList<>();        for (int i = 0; i < words.length; i++) {            if (words[i].length() == 0) {                for (Map.Entry
          
            entry : map.entrySet()) { if (isPalindrome(entry.getKey())) { addAll(indices, i, entry.getValue()); } } } for (int j = 0; j < words[i].length(); j++) { String front = words[i].substring(0, j); String back = words[i].substring(j, words[i].length()); String rfront = reverse(front); String rback = reverse(back); if (isPalindrome(front) && map.containsKey(rback)) { addAll(indices, map.get(rback), i); } if (isPalindrome(back) && map.containsKey(rfront)) { addAll(indices, i, map.get(rfront)); } } } return indices; } private void addAll(List
           
            
             > indices, int a, int b) { if (a == b) { return; } List
             
               list = new ArrayList<>(); list.add(a); list.add(b); indices.add(list); } private String reverse(String word) { return new StringBuilder(word).reverse().toString(); } private boolean isPalindrome(String word) { for (int i = 0, j = word.length() - 1; i < j; i++, j--) { if (word.charAt(i) != word.charAt(j)) { return false; } } return true; }}