336. Palindrome Pairs
Problem Description
The problem provides an array of unique strings and asks for the identification of all "palindrome pairs". A palindrome pair consists of two strings from the array that, when concatenated in any order, form a palindrome. A palindrome is a string that reads the same backward as forward.
Specifically, we're given two conditions for identifying a valid pair (i, j)
:
- Both
i
andj
are indices in the given array (within its length). - Concatenating
words[i]
withwords[j]
results in a palindrome, andi != j
.
The expected output is an array of all the indices of the words that form these palindrome pairs.
Additionally, the problem requires that the solution must be efficient, with a time complexity that is linear to the sum of all characters in all words in the array, which suggests that we can't afford to compare each possible pair explicitly due to the potential for this to create a time complexity that is quadratic relative to the number of words.
Intuition
To meet the time complexity requirement, we need to optimize the way we look for pairs. Instead of checking all possible pairs, we use a dictionary to store the words in a way where we can quickly lookup to see if the reverse of a string exists in the array.
Here's the intuition behind the strategy:
-
Pre-compute the reverse of each word: We need to know if the reverse of any substring of a word exists in the list of words. Creating a dictionary with the words as keys and their indices as values allows for quick lookups.
-
Detecting Palindrome Pairs:
- For every word, split the word into two parts,
a
andb
. - If the reverse of
a
is a word in our list andb
is a palindrome, then their concatenationa + b
forms a palindrome. - If the reverse of
b
is a word in our list anda
is a palindrome, thenb + a
also forms a palindrome. - We special-case empty strings, since any palindrome word will pair with it as both a prefix and a suffix.
- For every word, split the word into two parts,
-
Boundary Conditions:
- We should only add unique pairs: since we're iterating through each possible split of a word, ensure that we don't double-count pairs by checking the index.
- Handle empty words explicitly, as an empty string can form a palindrome with any palindrome word.
The provided solution iterates over each word and all its possible splits, applying this strategy to systematically construct a list of all palindrome pairs without redundant checks, thereby achieving the desired time complexity.
Learn more about Trie patterns.
Solution Approach
The implementation of the solution involves several steps, each exploiting properties of palindromes and efficient data structures to significantly reduce the computational complexity:
-
Dictionary Creation:
- A dictionary named
d
is created, where each key-value pair is a word fromwords
and its corresponding index. This allows for O(1) lookup time for any word in the array. The dictionary is constructed using a dictionary comprehension:d = {w: i for i, w in enumerate(words)}
.
- A dictionary named
-
Main Loop:
- We loop through each word
w
inwords
usingenumerate
to also keep track of the current indexi
.
- We loop through each word
-
Palindrome Splitting:
- In the inner loop, we consider all possible splits of
w
into two substringsa
andb
, such thatw = a + b
. This is achieved by iteratingj
from0
tolen(w) + 1
so we can include the case wherea
orb
could be an empty string.
- In the inner loop, we consider all possible splits of
-
Palindrome Checking and Pair Formation:
- We reverse
a
andb
to getra
andrb
and check the following:- If
ra
is ind
andb
is a palindrome (b == rb
),a + b
is a palindrome. We ensured[ra]
is not equal to the current indexi
to avoid pairing a word with itself. - If
rb
is ind
anda
is a palindrome (a == ra
), thenb + a
is a palindrome. We add a conditionj
to ensurea
is not an empty string because we want to avoid duplication of pairs that have already been added in the previous step.
- If
- When a valid palindrome pair is found, we append a list containing the indices
[i, d[ra]]
or[d[rb], i]
to the result listans
.
- We reverse
-
Return Results:
- After iterating through all words and their possible splits, the
ans
list, which contains all the found palindrome pairs, is returned.
- After iterating through all words and their possible splits, the
Several key algorithmic insights make this approach meet the necessary time complexity:
- Precomputation: Computing the reverse of strings only for the split parts rather than for entire words or for each word pair saves time.
- Efficient lookup: Using a hash table (the dictionary
d
) ensures that we can quickly check if the reverse of a substring exists in the original list of words. - String properties: Understanding that checking if two strings form a palindrome only requires checking if one part is the reverse of the other and the other part is a palindrome itself.
By leveraging these insights, the algorithm achieves the required time complexity of O(sum of words[i].length)
as it goes through each word and its characters at most twice.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a simple example to illustrate the solution approach. Suppose we have the following array of words:
1["bat", "tab", "cat"]
Our goal is to find all palindrome pairs among the given words.
-
Dictionary Creation:
We begin by creating a dictionary of word reverses for quick lookup:1d = {w[::-1]: i for i, w in enumerate(["bat", "tab", "cat"])} 2# d = {"tab": 0, "bat": 1, "tac": 2}
-
Main Loop:
We will then loop through each word in the original array:i = 0
,w = "bat"
i = 1
,w = "tab"
i = 2
,w = "cat"
-
Palindrome Splitting:
Considering all possible splits of, for example,"bat"
:- Split at j=0:
a = ""
,b = "bat"
- Split at j=1:
a = "b"
,b = "at"
- Split at j=2:
a = "ba"
,b = "t"
- Split at j=3:
a = "bat"
,b = ""
We repeat this for
"tab"
and"cat"
. - Split at j=0:
-
Palindrome Checking and Pair Formation:
We check according to the splits, for example, for"bat"
:- For a = "", b = "bat": Neither a nor b's reverse is found in d.
- For a = "b", b = "at": Neither a nor b's reverse is found in d.
- For a = "ba", b = "t": 'b' is found in d (it's the reverse of "tab"), and 'a' is a palindrome. Thus, ["ba" + "t"] forms a palindrome pair
["tab", "bat"]
, i.e., indices[1, 0]
. - For a = "bat", b = "": 'a' is found in d (it's the reverse of "tab") but don't add this as it's a duplicate pair of the previous step.
We do this for each word and take note of palindrome pairs without duplication:
- For
w = "bat"
, we find the pair[1, 0]
. - For
w = "tab"
, we find no new pairs (since "bat" + "tab" would be a duplicate of [1, 0]). - For
w = "cat"
, we find no pairs.
- Return Results:
The pairs list by now looks like this:
This is the final list of palindrome pairs.1ans = [[1, 0]]
Through this step-by-step approach, we efficiently find all the unique palindrome pairs in the given array without having to compare each string with every other string, ensuring the process runs in linear time relative to the sum of the lengths of all words.
Solution Implementation
1# The Solution class contains a method to find all unique pairs of indices such
2# that the concatenation of the two words at those indices forms a palindrome.
3class Solution:
4 def palindromePairs(self, words: List[str]) -> List[List[int]]:
5 # Create a dictionary to hold word to index mapping for quick lookup.
6 word_to_index = {word: index for index, word in enumerate(words)}
7 # This will hold the result β pairs of indices forming palindromes.
8 palindrome_pairs = []
9
10 # Loop over each word and its index.
11 for index, word in enumerate(words):
12 # Check each possible split of the word.
13 for j in range(len(word) + 1):
14 # Split the word into two parts.
15 left = word[:j]
16 right = word[j:]
17 # Reverse the left and right parts for comparison.
18 reversed_left = left[::-1]
19 reversed_right = right[::-1]
20
21 # Check if the reversed left part exists in the dictionary,
22 # and the right part is a palindrome, also ensure it's not the same word.
23 if reversed_left in word_to_index and word_to_index[reversed_left] != index and right == reversed_right:
24 palindrome_pairs.append([index, word_to_index[reversed_left]])
25
26 # Check if the reversed right part exists in the dictionary, and
27 # the left part is a palindrome, also ensure it's not the same word.
28 # We also check j to ensure we do not double-count palindromes.
29 if j > 0 and reversed_right in word_to_index and word_to_index[reversed_right] != index and left == reversed_left:
30 palindrome_pairs.append([word_to_index[reversed_right], index])
31
32 # Return the list of palindrome pairs.
33 return palindrome_pairs
34
1import java.util.List;
2import java.util.ArrayList;
3import java.util.Arrays;
4
5class Solution {
6 private static final int HASH_BASE = 131; // Define a prime number as the base for hash computations
7 private static final long[] POWER_CACHE = new long[310]; // Cache for powers of HASH_BASE
8 private static final int MODULO = (int) 1e9 + 7; // Define a large prime number for modulo operations to avoid overflow
9
10 // Static initializer block for precomputing the powers of HASH_BASE
11 static {
12 POWER_CACHE[0] = 1; // 1 is the 0th power of any number
13 for (int i = 1; i < POWER_CACHE.length; ++i) {
14 POWER_CACHE[i] = (POWER_CACHE[i - 1] * HASH_BASE) % MODULO;
15 }
16 }
17
18 // Method for finding all palindrome pairs in an array of words
19 public List<List<Integer>> palindromePairs(String[] words) {
20 int wordCount = words.length; // Number of words
21 long[] prefixHashes = new long[wordCount];
22 long[] suffixHashes = new long[wordCount];
23
24 // Precompute the prefix and suffix hashes for all words
25 for (int i = 0; i < wordCount; ++i) {
26 String word = words[i];
27 int wordLength = word.length();
28 for (int j = 0; j < wordLength; ++j) {
29 int prefixCharValue = word.charAt(j) - 'a' + 1;
30 int suffixCharValue = word.charAt(wordLength - j - 1) - 'a' + 1;
31 prefixHashes[i] = (prefixHashes[i] * HASH_BASE) % MODULO + prefixCharValue;
32 suffixHashes[i] = (suffixHashes[i] * HASH_BASE) % MODULO + suffixCharValue;
33 }
34 }
35
36 // Find and store all unique palindrome pairs
37 List<List<Integer>> palindromePairs = new ArrayList<>();
38 for (int i = 0; i < wordCount; ++i) {
39 for (int j = i + 1; j < wordCount; ++j) {
40 if (isPalindromePair(i, j, words[j].length(), words[i].length(), prefixHashes, suffixHashes)) {
41 palindromePairs.add(Arrays.asList(i, j));
42 }
43 if (isPalindromePair(j, i, words[i].length(), words[j].length(), prefixHashes, suffixHashes)) {
44 palindromePairs.add(Arrays.asList(j, i));
45 }
46 }
47 }
48 return palindromePairs;
49 }
50
51 // Helper method to check if the concatenation of two words results in a palindrome
52 private boolean isPalindromePair(int i, int j, int n, int m, long[] prefixHashes, long[] suffixHashes) {
53 long concatenatedPrefixHash = ((prefixHashes[i] * POWER_CACHE[n]) % MODULO + prefixHashes[j]) % MODULO;
54 long concatenatedSuffixHash = ((suffixHashes[j] * POWER_CACHE[m]) % MODULO + suffixHashes[i]) % MODULO;
55 return concatenatedPrefixHash == concatenatedSuffixHash; // Return true if both hashes match
56 }
57}
58
1#include <vector>
2#include <string>
3#include <array>
4
5class Solution {
6private:
7 static const int HASH_BASE = 131; // Define a prime number as the base for hash computations
8 static const int MODULO = 1000000007; // Define a large prime number for modulo operations to avoid overflow
9 static const std::array<long long, 310> POWER_CACHE; // Cache for powers of HASH_BASE
10
11public:
12 // Static function to initialize POWER_CACHE with powers of HASH_BASE
13 static std::array<long long, 310> createPowerCache() {
14 std::array<long long, 310> cache;
15 cache[0] = 1; // 1 is the 0th power of any number
16 for (size_t i = 1; i < cache.size(); ++i) {
17 cache[i] = (cache[i - 1] * HASH_BASE) % MODULO;
18 }
19 return cache;
20 }
21
22 // Method for finding all palindrome pairs in an array of words
23 std::vector<std::vector<int>> palindromePairs(const std::vector<std::string>& words) {
24 int wordCount = words.size(); // Number of words
25 std::vector<long long> prefixHashes(wordCount); // Store prefix hashes
26 std::vector<long long> suffixHashes(wordCount); // Store suffix hashes
27
28 // Precompute the prefix and suffix hashes for all words
29 for (int i = 0; i < wordCount; ++i) {
30 const std::string& word = words[i];
31 int wordLength = word.length();
32 for (int j = 0; j < wordLength; ++j) {
33 int prefixCharValue = word[j] - 'a' + 1;
34 int suffixCharValue = word[wordLength - j - 1] - 'a' + 1;
35 prefixHashes[i] = (prefixHashes[i] * HASH_BASE + prefixCharValue) % MODULO;
36 suffixHashes[i] = (suffixHashes[i] * HASH_BASE + suffixCharValue) % MODULO;
37 }
38 }
39
40 // Find and store all unique palindrome pairs
41 std::vector<std::vector<int>> palindromePairsList;
42 for (int i = 0; i < wordCount; ++i) {
43 for (int j = i + 1; j < wordCount; ++j) {
44 if (isPalindromePair(i, j, words[j].length(), words[i].length(), prefixHashes, suffixHashes)) {
45 palindromePairsList.push_back({i, j});
46 }
47 if (isPalindromePair(j, i, words[i].length(), words[j].length(), prefixHashes, suffixHashes)) {
48 palindromePairsList.push_back({j, i});
49 }
50 }
51 }
52 return palindromePairsList;
53 }
54
55 // Helper method to check if the concatenation of two words results in a palindrome
56 bool isPalindromePair(int i, int j, int wordLengthJ, int wordLengthI,
57 const std::vector<long long>& prefixHashes,
58 const std::vector<long long>& suffixHashes) {
59 long long concatenatedPrefixHash = (prefixHashes[i] * POWER_CACHE[wordLengthJ] + prefixHashes[j]) % MODULO;
60 long long concatenatedSuffixHash = (suffixHashes[j] * POWER_CACHE[wordLengthI] + suffixHashes[i]) % MODULO;
61 return concatenatedPrefixHash == concatenatedSuffixHash; // Return true if both hashes match
62 }
63};
64
65// Initialize the POWER_CACHE static member variable outside the class
66const std::array<long long, 310> Solution::POWER_CACHE = Solution::createPowerCache();
67
1const HASH_BASE: number = 131; // Define a prime number as the base for hash computations
2const POWER_CACHE: Array<number> = new Array<number>(310); // Cache for powers of HASH_BASE
3const MODULO: number = 1e9 + 7; // Define a large prime number for modulo operations to avoid overflow
4
5// Precompute the powers of HASH_BASE
6POWER_CACHE[0] = 1; // 1 is the 0th power of any number
7for (let i = 1; i < POWER_CACHE.length; i++) {
8 POWER_CACHE[i] = (POWER_CACHE[i - 1] * HASH_BASE) % MODULO;
9}
10
11// Function to find all palindrome pairs in an array of words
12function palindromePairs(words: string[]): number[][] {
13 const wordCount: number = words.length; // Number of words
14 const prefixHashes: Array<number> = new Array<number>(wordCount);
15 const suffixHashes: Array<number> = new Array<number>(wordCount);
16
17 // Precompute the prefix and suffix hashes for all words
18 for (let i = 0; i < wordCount; i++) {
19 const word: string = words[i];
20 const wordLength: number = word.length;
21 prefixHashes[i] = 0;
22 suffixHashes[i] = 0;
23 for (let j = 0; j < wordLength; j++) {
24 const prefixCharValue: number = word.charCodeAt(j) - 'a'.charCodeAt(0) + 1;
25 const suffixCharValue: number = word.charCodeAt(wordLength - j - 1) - 'a'.charCodeAt(0) + 1;
26 prefixHashes[i] = (prefixHashes[i] * HASH_BASE + prefixCharValue) % MODULO;
27 suffixHashes[i] = (suffixHashes[i] * HASH_BASE + suffixCharValue) % MODULO;
28 }
29 }
30
31 // Find and store all unique palindrome pairs
32 const palindromePairs: number[][] = [];
33 for (let i = 0; i < wordCount; i++) {
34 for (let j = i + 1; j < wordCount; j++) {
35 if (isPalindromePair(i, j, words[j].length, words[i].length, prefixHashes, suffixHashes)) {
36 palindromePairs.push([i, j]);
37 }
38 if (isPalindromePair(j, i, words[i].length, words[j].length, prefixHashes, suffixHashes)) {
39 palindromePairs.push([j, i]);
40 }
41 }
42 }
43 return palindromePairs;
44}
45
46// Helper function to check if the concatenation of two words results in a palindrome
47function isPalindromePair(
48 index1: number,
49 index2: number,
50 length1: number,
51 length2: number,
52 prefixHashes: Array<number>,
53 suffixHashes: Array<number>
54): boolean {
55 const concatenatedPrefixHash: number =
56 ((prefixHashes[index1] * POWER_CACHE[length1] + prefixHashes[index2]) % MODULO);
57 const concatenatedSuffixHash: number =
58 ((suffixHashes[index2] * POWER_CACHE[length2] + suffixHashes[index1]) % MODULO);
59 return concatenatedPrefixHash === concatenatedSuffixHash; // Return true if both hashes match
60}
61
Time and Space Complexity
Time Complexity
The time complexity of the given algorithm involves several nested operations within a loop that goes through all of the words, and for each word, iterates through all the possible splits. Here's a breakdown:
- We first create a dictionary
d
mapping each word to its index, which takesO(N * K)
time, whereN
is the number of words andK
is the average length of the words. - The outermost loop iterates
N
times, once for each word. - Within this loop, there is another loop that iterates
K + 1
times, whereK
is the length of the current word. - Inside the inner loop, we perform slices, reversals, and checks in the dictionary, each of which might take up to
O(K)
in time. - Thus, for each word, we perform
O(K^2)
work because of theK + 1
iterations and operations within them that could take up toO(K)
time. - There are
N
words, bringing the total toO(N * K^2)
.
Combining these together, we can conclude the overall time complexity of the function is O(N * K^2)
, incorporating both the setup of the dictionary and the nested loops for processing each word and its possible palindromic pairs.
Space Complexity
The space complexity is mainly determined by the storage used for the dictionary and the answer list:
- The dictionary
d
holds each word and its index, which requiresO(N)
space whereN
is the number of words. - The answer list
ans
which, in the worst case, can haveO(N^2)
pairs since each word could potentially form a palindrome with all other words.
Thus, we have the additional space complexity of O(N)
for the dictionary and O(N^2)
for the answer list, giving us O(N^2)
as the overall space complexity, which is a higher term and dominates the space usage.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question?Β Ask the Monster AssistantΒ anything you don't understand.
Still not clear? Β SubmitΒ the part you don't understand to our editors. Or join ourΒ Discord and ask the community.