Palindrome Pairs
You are given a 0-indexed array of unique strings words.
A palindrome pair is a pair of integers (i, j) such that:
0 <= i, j < words.length,
i != j, and
words[i] + words[j] (the concatenation of the two strings) is a palindrome.
Return an array of all the palindrome pairs of words.
You must write an algorithm with O(sum of words[i].length) runtime complexity.
There are multiple valid approaches but using a trie data structure is the simplest and most general option. Learning this will help with many difficult problems.
class Trie {
Integer endIndex;
Map<Character, Trie> child = new HashMap<>();
List<Integer> palindromesFromHere = new ArrayList<>();
boolean isWordNode() {
return endIndex != null;
}
}
class Solution {
private Trie buildTrie(String[] words) {
final Trie root = new Trie();
for (int i = 0, n = words.length; i < n; i++) {
final String currWord = words[i];
Trie currentTrie = root;
for (int j = 0, jn = currWord.length(); j < jn; j++) {
final int reverseIndex = jn - j - 1;
if (isPalindrome(currWord, 0, reverseIndex)) currentTrie.palindromesFromHere.add(i);
final Character currReverseChar = currWord.charAt(reverseIndex);
currentTrie = currentTrie.child.computeIfAbsent(currReverseChar, c -> new Trie());
}
currentTrie.endIndex = i;
}
return root;
}
public List<List<Integer>> palindromePairs(String[] words) {
final Trie root = buildTrie(words);
final List<List<Integer>> pairs = new ArrayList<>();
outer: for (int i = 0, n = words.length; i < n; i++) {
final String currWord = words[i];
Trie currentTrie = root;
for (int j = 0, jn = currWord.length(); j < jn; j++) {
// case 3 : When W1 is bigger than W2 and W1 ends with palindrome
if (currentTrie.isWordNode() && isPalindrome(currWord, j, jn - 1)) {
pairs.add(Arrays.asList(i, currentTrie.endIndex));
}
// move to next trie
currentTrie = currentTrie.child.get(currWord.charAt(j));
if (currentTrie == null) continue outer;
}
// case 1 : W1 and W2 are of same size and reverse of each other
if (currentTrie.isWordNode() && currentTrie.endIndex != i) {
pairs.add(Arrays.asList(i, currentTrie.endIndex));
}
// case 2 : W1 is smaller than W2 and W2 begins with palindrome
for (final Integer palindromeIndex : currentTrie.palindromesFromHere) {
pairs.add(Arrays.asList(i, palindromeIndex));
}
}
return pairs;
}
private boolean isPalindrome(String word, int fromIndex, int toIndex) {
for (int i = fromIndex, j = toIndex; i < j; i++, j--) {
if (word.charAt(i) != word.charAt(j)) return false;
}
return true;
}
}Related Problems
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Given a 1-indexed integer array prices, where prices[i] is the price of a particular stock on the ith day, your task is to select some of the elements of prices such that your selection is linear.
A selection indexes, where indexes is a 1-indexed integer array of length k which is a subsequence of the array [1, 2, ..., n], is linear if:
For every 1 < j <= k, prices[indexes[j]] - prices[indexes[j - 1]] == indexes[j] - indexes[j - 1]
The score of a linear selection is the sum of the prices at those indices, return the maximum score that a linear selection can have given the input.
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.