336. Palindrome Pairs

HardTrieArrayHash TableString

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 and j are indices in the given array (within its length).
Concatenating words[i] with words[j] results in a palindrome, and i != 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 and b.
- If the reverse of a is a word in our list and b is a palindrome, then their concatenation a + b forms a palindrome.
- If the reverse of b is a word in our list and a is a palindrome, then b + 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.
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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimumsAdd a heap to store the minimumsAdd a variable to track the minimumAdd a queue to store the minumums

I don’t know

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 from words 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)}.
Main Loop:
- We loop through each word w in words using enumerate to also keep track of the current index i.
Palindrome Splitting:
- In the inner loop, we consider all possible splits of w into two substrings a and b, such that w = a + b. This is achieved by iterating j from 0 to len(w) + 1 so we can include the case where a or b could be an empty string.
Palindrome Checking and Pair Formation:
- We reverse a and b to get ra and rb and check the following:
  - If ra is in d and b is a palindrome (b == rb), a + b is a palindrome. We ensure d[ra] is not equal to the current index i to avoid pairing a word with itself.
  - If rb is in d and a is a palindrome (a == ra), then b + a is a palindrome. We add a condition j to ensure a is not an empty string because we want to avoid duplication of pairs that have already been added in the previous step.
- When a valid palindrome pair is found, we append a list containing the indices [i, d[ra]] or [d[rb], i] to the result list ans.
Return Results:
- After iterating through all words and their possible splits, the ans list, which contains all the found palindrome pairs, is returned.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example 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".
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:
```
1ans = [[1, 0]]
```
This is the final list of palindrome pairs.

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

Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

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 takes O(N * K) time, where N is the number of words and K 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, where K 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 the K + 1 iterations and operations within them that could take up to O(K) time.
There are N words, bringing the total to O(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 requires O(N) space where N is the number of words.
The answer list ans which, in the worst case, can have O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

336. Palindrome Pairs

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings