Palindrome Pairs

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"]

This one doesn't look like a hard one: the easiest way is to go through the whole array and find the solution. Yet it definitely will exceed time limit. A smarter way is first to use a map and store all the words and their positions. Then go through the list and find the following pattern:

1. If the word is palindrome, find if there is empty string exists.

2. Find if the reverse word exists in the list. 

3. For each word, traverse through the word and separate them to two parts: if one of the two parts is palindrome, find if there exists the reverse word of the other part. 

4. Make sure the position of the words are different. 

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> rst = new ArrayList<>();
        if (words == null || words.length == 0)
            return rst;
        Map<String, Integer> positions = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            positions.put(words[i], i);
        }
        for (int i = 0; i < words.length; i++) {
            String s = words[i];
            String rs = reverse(s);
            if (isPalindrome(s, "") && positions.containsKey("")) {
                int pos = positions.get("");
                if (pos != i) {
                    addToList(rst, i, pos);
                    addToList(rst, pos, i);
                }
                
            }
                
            if (positions.containsKey(rs) && positions.get(rs) != i) {
                int pos = positions.get(rs);
                addToList(rst, i, pos);
            }
                
            for (int j = 1; j < s.length(); j++) {
                String left = s.substring(0, j);
                String right = s.substring(j, s.length());
                String r_left = reverse(left);
                String r_right = reverse(right);
                if (isPalindrome(left, "") && positions.containsKey(r_right))
                    addToList(rst, positions.get(r_right),i);
                if (isPalindrome(right, "") && positions.containsKey(r_left))
                    addToList(rst, i, positions.get(r_left));
                    
            }
        }
        return rst;
    }
    
    private void addToList(List<List<Integer>> rst, int first, int second) {
        List<Integer> curr = new ArrayList<Integer>();
        curr.add(first);
        curr.add(second);
        rst.add(curr);
    }
    
    private boolean isPalindrome(String a, String b) {
        String ab = a + b;
        int start = 0;
        int end = ab.length() - 1;
        while (start < end) {
            if (ab.charAt(start) != ab.charAt(end))
                return false;
            start++;
            end--;
        }
        return true;
    }
    
    private String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}