# 336. Palindrome Pairs

[Link](https://leetcode.com/problems/palindrome-pairs/description/)

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:**

```
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
```

**Example 2:**

```
Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]
```

**Solution**

針對每個word尋找其中是否有某個部分可以自己回文。ex: **ada**ras, 其中**ada已經是回文了。**\
此時，若能找到其他word剛好剩下沒有回文的部分(ex:ras)的revert那麼這兩個組合就可以成為一個回文:

ex:\
words\[i]: ada**ras** , words\[j]:**sar**\
那麼 \[j, i]就可以組成一個回&#x6587;**: sar**ada**ras**\
\
words\[i]: **ras**ada , words\[j]:**sar**\
那麼 \[i, j]就可以組成一個回&#x6587;**: ras**ada**sar**

Time complexity O(m \* n ^ 2) where m is the length of the list and the n is the length of the word.

```
public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ret = new LinkedList<>();
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++){
            map.put(words[i], i);
        }
        
        for(int i = 0; i < words.length; i++){
            String target = words[i];
            for(int j = 0; j <= target.length(); j++){
                String preString = target.substring(0,j);
                String postString = target.substring(j);
                if(isPalindrome(preString)){
                    String revertPostString = new StringBuilder(postString).reverse().toString();
                    if(map.containsKey(revertPostString) && map.get(revertPostString) != i){
                        LinkedList<Integer> list = new LinkedList<>();
                        list.add(map.get(revertPostString));
                        list.add(i);
                        ret.add(list);
                    }
                }
                if(isPalindrome(postString)){
                    String revertPostString = new StringBuilder(preString).reverse().toString();
                    if(map.containsKey(revertPostString) && map.get(revertPostString) != i && postString.length()!=0){
                        LinkedList<Integer> list = new LinkedList<>();
                        list.add(i);
                        list.add(map.get(revertPostString));
                        ret.add(list);
                    }
                }
            }
        }
        return ret;
    }

    private boolean isPalindrome(String string) {
        int i = 0, j = string.length() - 1;
        while(j >= i){
            if(string.charAt(i) != string.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
```
