336. Palindrome Pairs

336. Palindrome Pairs

Hard

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

------------------------
对每一个string，把它拼成palindrome所需要的另一半都计算出来，然后在给定的范围内查找。

O(n * k^2), n为string的格式，k为string的平均长度。k^2的消耗在isPalindrome

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> map = getMap(words);
        List<List<Integer>> rt = new ArrayList<>();
        
        for (int start = 0; start < words.length; start++) {
            String word = words[start];
            for (int i = 0; i <= word.length(); i++) {
                String st1 = word.substring(0,i);
                String st2 = word.substring(i);
                
                if (isPalindrome(st1)) {
                    String target = new StringBuilder(st2).reverse().toString();
                    if (map.containsKey(target) && map.get(target) != start) {
                        List<Integer> l = new ArrayList<>();
                        l.add(map.get(target));    
                        l.add(start);
                        rt.add(l);
                    }
                }
                
                if (isPalindrome(st2) && !st2.isEmpty()) {
                    String target = new StringBuilder(st1).reverse().toString();
                    if (map.containsKey(target) && map.get(target) != start) {
                        List<Integer> l = new ArrayList<>();
                        l.add(start);
                        l.add(map.get(target));    
                        rt.add(l);
                    }
                }
            }
        }
        
        return rt;
    }
    
    private boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        
        return true;
    }
    
    
    private Map<String, Integer> getMap(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }
        
        return map;
    }
}