https://leetcode.com/problems/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"]
Time Complexity : O(n^2*k) // and k be the length of the longest word.
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> pairs = new ArrayList();
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words.length; j++) {
if (i == j) continue;
String combined = words[i].concat(words[j]);
String reversed = new StringBuilder(combined).reverse().toString();
if (combined.equals(reversed)) {
pairs.add(Arrays.asList(i, j));
}
}
}
return pairs;
}
}Time: O(k^2 * n)
Space: O((k+n)^2)
Three Cases:
- Check if the reverse of word is present. If it is, then we have a case 1 pair by appending the reverse onto the end of word.
- For each suffix of word, check if the suffix is a palindrome. if it is a palindrome, then reverse the remaining prefix and check if it's in the list. If it is, then this is an example of case 2.
- For each prefix of word, check if the prefix is a palindrome. if it is a palindrome, then reverse the remaining suffix and check if it's in the list. If it is, then this is an example of case 3.
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
Map<String, Integer> wordSet = new HashMap<>();
for (int i = 0; i < words.length; i++) {
wordSet.put(words[i], i);
}
List<List<Integer>> solution = new ArrayList();
for (String word: wordSet.keySet()) {
int currentWordIndex = wordSet.get(word);
String reversedWord = new StringBuilder(word).reverse().toString();
// case #1
if (wordSet.containsKey(reversedWord)
&& wordSet.get(reversed) != currentWordIndex) {
solution.add(Arrays.asList(currentWordIndex, wordSet.get(reversedWord)));
}
// case #2
for (String suffix: allValidSuffixes(word)) {
String reversedSuffix = new StringBuilder(suffix).reverse().toString();
if (wordSet.containsKey(reversedSuffix)) {
solution.add(Arrays.asList(wordSet.get(reversedSuffix), currentWordIndex));
}
}
// case #3
for (String prefix: allValidPrefixed(word)) {
String reversedPrefix = new StringBuilder(prefix).reverse().toString();
if (wordSet.containsKey(reversedPrefix)) {
solution.add(Arrays.asList(currentWordIndex, wordSet.get(reversedPrefix)));
}
}
}
return solution;
}
private List<String> allValidPrefixes(String word) {
List<String> validPrefixes = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
if (isPalindromeBetween(word, i, word.length() - 1)) {
validPrefixes.add(word.substring(0, i));
}
}
return validPrefixes;
}
private List<String> allValidSuffixes(String word) {
List<String> validSuffixes = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
if (isPalindromeBetween(word, 0, i)) {
validSuffixes.add(word.substring(i + 1, word.length()));
}
}
return validSuffixes;
}
// Is the prefix ending at i a palindrome?
private boolean isPalindromeBetween(String word, int front, int back) {
while (front < back) {
if (word.charAt(front) != word.charAt(back)) return false;
front++;
back--;
}
return true;
}
}class TrieNode {
public int wordEnding = -1;
public Map<Character, TrieNode> next = new HashMap();
public List<Integer> palindromePrefixRemaining = new ArrayList();
}
class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
TrieNode trie = new TrieNode();
// 1. build the Trie with reversed words
for (int wordId = 0; wordId < words.length; wordId++) {
String word = words[wordId];
String reversedWord = new StringBuilder(word).reverse().toString();
TrieNode currentTrieLevel = trie;
for (int j = 0; j < reversedWord.length(); j++) {
if (hasPalindromeRemaining(reversedWord, j)) {
currentTrieLevel.palindromePrefixRemaining.add(wordId);
}
Character c = reversedWord.charAt(j);
if (!currentTrieLevel.next.containsKey(c)) {
currentTrieLevel.next.put(c, new TrieNode());
}
currentTrieLevel = currentTrieLevel.next.get(c);
}
currentTrieLevel.wordEnding = wordId;
}
// 2. Find Pairs
List<List<Integer>> pairs = new ArrayList<>();
for (int wordId = 0; wordId < words.length; wordId++) {
String word = words[wordId];
TrieNode currentTrieLevel = trie;
for (int j = 0; j < word.length(); j++) {
// case #3: word:(xxx + Palindrome), trie: xxx
if (currentTrieLevel.wordEnding != -1
&& hasPalindromeRemaining(word, j)) {
pairs.add(Arrays.asList(wordId, currentTrieLevel.wordEnding));
}
Character c = word.charAt(j);
currentTrieLevel = currentTrieLevel.next.get(c);
if (currentTrieLevel == null) break;
}
if (currentTrieLevel == null) continue;
// case #1
if (currentTrieLevel.wordEnding != -1
&& currentTrieLevel.wordEnding != wordId) {
pairs.add(Arrays.asList(wordId, currentTrieLevel.wordEnding));
}
// case #2: Trie:(Palindrome + xxx) , word:xxx
for (int other: currentTrieLevel.palindromePrefixRemaining) {
pairs.add(Arrays.asList(wordId, other));
}
}
return pairs;
}
private boolean hasPalindromeRemaining(String s, int i) {
int p1 = i;
int p2 = s.length() - 1;
while (p1 < p2) {
if (s.charAt(p1) != s.charAt(p2)) return false;
p1++;
p2--;
}
return true;
}
}