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

Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution

public class Solution {
     public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        if (words == null || words.length == 0) return result;

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }

        if (map.containsKey("")) {
            int index = map.get("");
            for (int i = 0; i < words.length; i++) {
                if (index != i && isPalindrome(words[i], 0, words[i].length() - 1)) {
                    List<Integer> temp1 = new ArrayList<>();
                    temp1.add(index);
                    temp1.add(i);

                    List<Integer> temp2 = new ArrayList<>();
                    temp2.add(i);
                    temp2.add(index);

                    result.add(temp1);
                    result.add(temp2);
                }
            }
        }

        // reverse string to each other
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if (checkReverse(words[i], words[j])) {
                    List<Integer> temp1 = new ArrayList<>();
                    temp1.add(i);
                    temp1.add(j);

                    List<Integer> temp2 = new ArrayList<>();
                    temp2.add(j);
                    temp2.add(i);

                    result.add(temp1);
                    result.add(temp2);
                }
            }
        }

        // another two cases
        for (int i = 0; i < words.length; i++) {
            String currentString = words[i];

            for (int j = 0; j < currentString.length() - 1; j++) {
                if (isPalindrome(currentString, 0, j)) {
                    String reverseString = reverse(currentString.substring(j + 1));
                    if (map.containsKey(reverseString)) {
                        List<Integer> temp2 = new ArrayList<>();
                        temp2.add(map.get(reverseString));
                        temp2.add(i);

                        result.add(temp2);
                    }
                }
            }

            for (int j = 1; j < currentString.length(); j++) {
                if (isPalindrome(currentString, j, currentString.length() - 1)) {
                    String reverseString = reverse(currentString.substring(0, j));
                    if (map.containsKey(reverseString)) {
                        List<Integer> temp2 = new ArrayList<>();
                        temp2.add(i);

                        temp2.add(map.get(reverseString));

                        result.add(temp2);
                    }
                }
            }
        }

        return result;
    }

    private String reverse(String s) {
        StringBuffer sb = new StringBuffer(s);
        return sb.reverse().toString();
    }

    private boolean isPalindrome(String s, int start, int end) {
        if (start > end) return false;
        if (start == end) return true;

        while (start < end) {
            char c1 = s.charAt(start);
            char c2 = s.charAt(end);
            if (c1 != c2) {
                return false;
            }

               start++;
            end--;
        }
        return true;
    }

    private boolean checkReverse(String s1, String s2) {
        if (s1.length() != s2.length()) return false;

        int size = s1.length();
        for (int i = 0; i < size; i++) {
            if (s1.charAt(i) != s2.charAt(size - i - 1)) {
                return false;
            }
        }

        return true;
    }
}