Palindrome Pairs

LeetCode Q 336 - 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:
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

The idea is we first store each string and its index in the map.
Then, for each string, we divide it into two substrings(str1 and str2), and check all the substring pairs.

1. if str1 is Palindrome, then we reverse str2, and check if the map containsKey reversedStr2. If it contains, then we can concate String reversedStr2 and str1 to get the palindrome string. Note: the reversedStr2 should be on the left and str1 on the right.
2. if str2 is Palindrome, then we reverse str1, and check if the map containsKey reversedStr1. If it contains, then we can concate String str2 and reversedStr1 to get the palindrome string. Note: the str2 should be on the left and reversedStr1 on the right.

Caution: MUST CHECK whether str.length() is equal to 0 in either if statement, because we need to make sure we do not add duplicate pairs (if str1.length() == 0, both of str1 and str2 will from input array).

Code:

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

	Map<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 word = words[i];
		for (int j = 0; j <= word.length(); j++) {
			String str1 = word.substring(0, j);
			String str2 = word.substring(j);
			
			if (isPalindrome(str1)) {
				String reversedStr2 = new StringBuilder(str2).reverse().toString();
				if (map.containsKey(reversedStr2) && map.get(reversedStr2) != i && j != 0)
					res.add(Arrays.asList(map.get(reversedStr2), str1));
			}

			if (isPalindrome(str2)) {
				String reversedStr1 = new StringBuilder(str1).reverse().toString();
				if (map.containsKey(reversedStr1) && map.get(reversedStr1) != i)
					res.add(Arrays.asList(i,map.get(reversedStr1)));   
			}
		}
	}

	return res;
}

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