## Thursday, November 26, 2015

### Airbnb: Palindromic pair of a list of strings

LeetCode 336 - Palindrome Pairs
Buttercola: Airbnb: Palindromic pair of a list of strings
Given a list of strings, find all the palindromic pairs of the string and output the concatenated palindrome.

e.g. [abc, cba], output is abccba, cbaabc.
e.g. [aabc, cb], output is cbaabc

Understand the problem:

The brute-force solution to this problem is very simple. For each word, we search all the others and see if it can form a palindrome. Assume that the ave. length of each word is m and there are totally n words in the list, the time complexity would be O(n^2 * m).

Solution:
A better solution is for a given word, we put all its possible words which can form a palindrome into a HashMap. Then for another word, if it is in the map, we know that it is a pair which can forma a palindrome. Note that a word can form a palindrome from front and end, e.g. [abc, cba], the palindrome could be either abccba and cbaabc. So we need to maintain two maps and store the candidate words which can be in the front and end.
The key of the map is the candidate words, and the value is the list of the original words.
`  ``public` `List<String> getPalindromicPairs(String[] input) {`
`    ``List<String> result = ``new` `ArrayList<>();`
`    ``if` `(input == ``null` `|| input.length < ``2``) {`
`      ``return` `result;`
`    ``}`
`    `
`    ``// Step 1: add all the revsered order of all `
`    ``// words into the set`
`    ``Map<String, Integer> map = ``new` `HashMap<>();`
`    ``for` `(String str : input) {`
`      ``String reverseStr = reverse(str);`
`      ``if` `(!map.containsKey(reverseStr)) {`
`        ``map.put(reverseStr, ``1``);`
`      ``} ``else` `{`
`        ``map.put(reverseStr, map.get(reverseStr) + ``1``);`
`      ``}`
`    ``}`
`    `
`    ``for` `(String str : input) {`
`      ``// Iterate all prefix`
`      ``for` `(``int` `i = ``1``; i <= str.length(); i++) {`
`        ``String prefix = str.substring(``0``, i);`
`        ``String postfix = str.substring(i);`
`        `
`        ``if` `(map.containsKey(prefix) && isPalindrome(postfix)) {`
`          ``String reversedStr = reverse(prefix);`
`          ``if` `(!prefix.equals(reversedStr) || (prefix.equals(reversedStr) && map.get(prefix) % ``2` `== ``0``)) {`
`            ``String tmp = str + reverse(prefix);`
`            ``result.add(tmp);`
`          ``}`
`        ``}`
`      ``}`
`      `
`      ``// Iterate all postfix`
`      ``for` `(``int` `i = str.length() - ``1``; i >= ``0``; i--) {`
`        ``String postfix = str.substring(i);`
`        ``String prefix = str.substring(``0``, i);`
`        `
`        ``if` `(map.containsKey(postfix) && isPalindrome(prefix)) {`
`          ``String rePostfix = reverse(postfix);`
`          ``if` `(!postfix.equals(rePostfix) || (postfix.equals(rePostfix) && map.get(postfix) % ``2` `== ``0``)) {`
`           ``String tmp = reverse(postfix) + str;`
`           ``result.add(tmp);`
`          ``}`
`        ``}`
`      ``}`
`    ``}`
`    `
`    ``return` `result;`
`    `
`  ``}`
`  `
`  ``private` `String reverse(String s) {`
`    ``if` `(s == ``null` `|| s.length() == ``0``) {`
`      ``return` `s;`
`    ``}`
`    `
`    ``char``[] arr = s.toCharArray();`
`    ``int` `lo = ``0``;`
`    ``int` `hi = arr.length - ``1``;`
`    `
`    ``while` `(lo < hi) {`
`      ``char` `temp = arr[lo];`
`      ``arr[lo] = arr[hi];`
`      ``arr[hi] = temp;`
`      `
`      ``lo++;`
`      ``hi--;`
`    ``}`
`    `
`    ``return` `new` `String(arr);`
`  ``}`
`  `
`  ``private` `boolean` `isPalindrome(String s) {`
`    ``if` `(s == ``null` `|| s.length() <= ``1``) {`
`      ``return` `true``;`
`    ``}`
`    `
`    ``int` `lo = ``0``;`
`    ``int` `hi = s.length() - ``1``;`
`    `
`    ``while` `(lo < hi) {`
`      ``if` `(s.charAt(lo) != s.charAt(hi)) {`
`        ``return` `false``;`
`      ``}`
`      `
`      ``lo++;`
`      ``hi--;`
`    ``}`
`    `
`    ``return` `true``;`
`  ``}`

Palindrome Pairs – AlgoBox by dietpepsi
Given a list of unique words. Find all pairs of 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"]`
Put all words in a Set. For each word, get all it’s prefix and suffix. Search for reversed(prefix) and reversed(suffix) in the Set.
If found, check if the rest of the string is a palindrome or not. Time complexity $O(nk^2)$.
public List<List<Integer>> parlindromePairs(String[] words) {
List<List<Integer>> ans = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; ++i) map.put(words[i], i);
for (int k = 0; k < words.length; ++k) {
String word = words[k];
int n = word.length();
for (int i = 0; i < n + 1; ++i) {
String suffix = new StringBuilder(word.substring(0, i)).reverse().toString();
String prefix = new StringBuilder(word.substring(i, n)).reverse().toString();
if (i != 0 && map.containsKey(prefix) && map.get(prefix) != k && isPalindrome(suffix))
if (map.containsKey(suffix) && map.get(suffix) != k && isPalindrome(prefix))
}
}
return ans;
}
public boolean isPalindrome(String word) {
for (int i = 0; i < word.length() / 2; ++i)
if (word.charAt(i) != word.charAt(word.length() - i - 1)) return false;
return true;
}

#### Method 2

1. Preprocess all words using Manacher’s Algorithm and save the results. The step is O(nk).
2. Build a Trie of all words. O(nk).
3. For each word search reversed word in the trie, if found partial match, use the preprocess results to check if the rest of the string is a palindrome in O(1). The step is O(nk).
4. Build a Trie of all reversed words. O(nk).
5. For each word search it in the reversed Trie, if found partial match, use the preprocess results to check if the rest of the string is a palindrome in O(1). The step is O(nk).

Total time complexity is $O(nk)$.