336. Palindrome Pairs¶

Problem:¶

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

Solutions:¶

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        HashMap<String, Integer> index = new HashMap<String, Integer>();
        for (int i = 0; i < words.length; i ++) {
            index.put(words[i], i);
        }
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        for (int i = 0; i < words.length; i ++) {
            String reverse = new StringBuilder(words[i]).reverse().toString();
            int start = 0, end = reverse.length();
            if (index.containsKey(reverse) && index.get(reverse) != i) {
                List<Integer> tmp = new LinkedList<Integer>();
                tmp.add(index.get(reverse));
                tmp.add(i);
                res.add(tmp);
                start ++;
                end --;
            }

            for (int j = start; j <= end; j ++) {
                String left = reverse.substring(0, j);
                String right = reverse.substring(j);
                if (index.containsKey(left) && index.get(left) != i && isPa(right)) {
                    List<Integer> tmp = new LinkedList<Integer>();
                    tmp.add(index.get(left));
                    tmp.add(i);
                    res.add(tmp);
                }
                if (index.containsKey(right) && index.get(right) != i && isPa(left)) {
                    List<Integer> tmp = new LinkedList<Integer>();
                    tmp.add(i);
                    tmp.add(index.get(right));
                    res.add(tmp);
                }
            }
        }
        return res;
    }
    private boolean isPa(String s) {
        if (s.equals("")) {
            return true;
        }
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}