Palindrome Pairs
Description
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.
Hint
Train of Thought
Added: a (not so) naive solution
If two concatenated words form a palindrome, then there are three cases to consider:
+---s1---+---s2--+ +---s1---+-s2-+ +-s1-+---s2---+ |abcdefgh|hgfedcba| |abcdxyyx|dcba| |abcd|xyyxdcba| Case 1 is when one string is a mirror image of another. Case 2 is when the first string is longer than the other and consists of the mirror image of the other (prefix) and a palindrome (suffix). Case 3 is a mirror image of case 2. Case 1 can also be considered a special subcase of either case 2 or case 3 with an empty palindrome suffix/prefix.
Of these three, case 1 is definitely the easiest because we just need to look up a word in a reverse string-to-index map (words are unique, so no multimaps needed). If we iterate over the list with s1 as the current string, then case 2 is also much easier than case 3 because when we locate a prefix/palindrome split inside s1 we just need to look up for the reversed prefix in the map.
Case 3 is trickier, but we can get rid of case 3 altogether if we just make another run with the reversed words! This way case 3 turns into case 2. We only need to consider case 1 in one of these runs in order to avoid duplicate combinations. With that in mind, I present the following 154 ms solution:
Code
public List<List<Integer>> palindromePairs(String[] words) {
Map<String, Integer> index = new HashMap<>();
Map<String, Integer> revIndex = new HashMap<>();
String[] revWords = new String[words.length];
for (int i = 0; i < words.length; ++i) {
String s = words[i];
String r = new StringBuilder(s).reverse().toString();
index.put(s, i);
revIndex.put(r, i);
revWords[i] = r;
}
List<List<Integer>> result = new ArrayList<>();
result.addAll(findPairs(words, revWords, revIndex, false));
result.addAll(findPairs(revWords, words, index, true));
return result;
}
private static List<List<Integer>> findPairs(String[] words, String[] revWords, Map<String, Integer> revIndex, boolean reverse) {
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < words.length; ++i) {
String s = words[i];
for (int k = reverse ? 1 : 0; k <= s.length(); ++k) { // check suffixes, <= because we allow empty words
Integer j = revIndex.get(s.substring(k));
if (j != null && j != i) { // reversed suffix is present in the words list
// check whether the prefix is a palindrome
if (s.regionMatches(0, revWords[i], s.length() - k, k)) {
result.add(reverse ? Arrays.asList(i, j) : Arrays.asList(j, i));
}
}
}
}
return result;
}