336. Palindrome Pairs - Detailed Explanation
Problem Statement
Given a list of unique words, find all pairs of distinct indices (i, j) such that the concatenation of words[i] + words[j] forms a palindrome.
A string is a palindrome if it reads the same backward as forward.
Example 1
- Input: words = ["abcd", "dcba", "lls", "s", "sssll"]
- Output: [[0, 1], [1, 0], [3, 2], [2, 4]]
- Explanation:
- words[0] + words[1] → "abcd" + "dcba" = "abcddcba", which is a palindrome.
- words[1] + words[0] → "dcba" + "abcd" = "dcbaabcd", which is also a palindrome.
- words[3] + words[2] → "s" + "lls" = "slls" forms a palindrome.
- words[2] + words[4] → "lls" + "sssll" = "llssssll" is a palindrome.
Example 2
- Input: words = ["bat", "tab", "cat"]
- Output: [[0, 1], [1, 0]]
- Explanation:
- words[0] + words[1] → "bat" + "tab" = "battab", which is a palindrome.
- words[1] + words[0] → "tab" + "bat" = "tabbat", which is a palindrome.
Example 3
- Input: words = ["a", ""]
- Output: [[0, 1], [1, 0]]
- Explanation:
- "a" + "" = "a" is a palindrome.
- "" + "a" = "a" is also a palindrome.
Constraints
- 1 <= words.length <= 5000
- 0 <= words[i].length <= 300
- words[i] consists of lower-case English letters.
- All words are unique.
Hints
-
Substring Palindrome Check:
Think about how you can determine if a substring is a palindrome. Splitting each word into two parts (prefix and suffix) and checking whether one part is a palindrome can help you identify potential pairs. -
Using a Hash Map for Reverse Lookup:
Consider storing each word's reverse in a hash map. Then for every word in the list, try splitting it at every possible position. If one part is a palindrome, check whether the reverse of the other part exists in the map. This technique avoids checking every pair explicitly.
Approach 1: Brute Force Simulation
Explanation
The simplest approach is to consider every pair of distinct words and check if their concatenation is a palindrome. This involves:
- Iterating over all pairs (i, j) with i ≠ j.
- Concatenating words[i] + words[j].
- Checking if the resulting string is a palindrome.
Step-by-Step Walkthrough
Consider words = ["bat", "tab", "cat"]:
- For pair (0, 1): "bat" + "tab" = "battab" → palindrome.
- For pair (1, 0): "tab" + "bat" = "tabbat" → palindrome.
- All other pairs do not form a palindrome.
Complexity Analysis
- Time Complexity: O(n² * k) where n is the number of words and k is the average length of the words.
- Space Complexity: O(1) additional space (ignoring output).
Python Code (Brute Force)
Java Code (Brute Force)
Approach 2: Optimal Hash Map with Palindrome Check
Explanation
To optimize the solution, we use a hash map (or dictionary) to store each word's reverse along with its index. This allows us to quickly determine if a complementary substring exists that can form a palindrome with the current word.
Steps Involved
-
Hash Map Setup:
Create a hash map where the key is the reversed word and the value is the index of that word. -
Iterate Through Each Word:
For each word in the list, try every possible split position. Split the word into two parts:- Prefix: The substring before the split.
- Suffix: The substring after the split.
-
Check for Palindrome Conditions:
- Case 1: If the prefix is a palindrome, then check if the reverse of the suffix exists in the hash map (and is not the current word). If it exists, then the reverse of the suffix can be placed before the current word to form a palindrome.
- Case 2: If the suffix is a palindrome, then check if the reverse of the prefix exists in the hash map (and is not the current word). If it exists, then the reverse of the prefix can be placed after the current word to form a palindrome.
-
Handle the Empty String Case:
The empty string is a special case since any palindrome word can form a valid pair with the empty string.
Step-by-Step Walkthrough
Consider words = ["abcd", "dcba", "lls", "s", "sssll"]:
- Build a map:
- "dcba" → 0 (reverse of "abcd")
- "abcd" → 1 (reverse of "dcba")
- "sll" → 2 (reverse of "lls")
- "s" → 3 (reverse of "s")
- "llsss" → 4 (reverse of "sssll")
- For each word, try every possible split:
- For "abcd":
- Split into "" and "abcd".
- "" is a palindrome. Check if "dcba" (reverse of "abcd") exists → yes, index 1 → add pair [1, 0].
- Split into "a" and "bcd", "ab" and "cd", "abc" and "d". Check each for palindrome properties.
- Split into "" and "abcd".
- Continue similarly for other words.
- For "abcd":
Complexity Analysis
-
Time Complexity:
O(n * k²) in the worst case, where n is the number of words and k is the average length of each word. This is because for each word we try every possible split and check if a substring is a palindrome. -
Space Complexity:
O(n * k) for the hash map storing reversed words.
Python Code (Optimal Approach)
Java Code (Optimal Approach)
Step-by-Step Walkthrough and Visual Examples
Let’s walk through the optimal approach with the example words = ["abcd", "dcba", "lls", "s", "sssll"]:
-
Build the Hash Map:
- Reverse each word and store with its index:
- "abcd" → reverse "dcba" → map["dcba"] = 0
- "dcba" → reverse "abcd" → map["abcd"] = 1
- "lls" → reverse "sll" → map["sll"] = 2
- "s" → reverse "s" → map["s"] = 3
- "sssll" → reverse "llsss" → map["llsss"] = 4
- Reverse each word and store with its index:
-
Process each word by trying every split:
- For "abcd" (index 0):
- Split at position 0: prefix = "", suffix = "abcd".
- "" is a palindrome. Check if "abcd" exists in map → found index 1. Add pair [1, 0].
- Continue with other splits checking if either the prefix or suffix is a palindrome and looking up the corresponding reverse.
- Split at position 0: prefix = "", suffix = "abcd".
- For "abcd" (index 0):
-
Handle duplicates and edge cases:
- When the split reaches the end of the word, ensure not to count the same pair twice.
- Special care is taken for the empty string case.
Common Mistakes and Edge Cases
-
Not Handling Empty Strings:
Failing to check when a word is empty can lead to missing valid pairs because every palindrome word can pair with an empty string. -
Duplicate Pairs:
Be careful to avoid adding the same pair twice. Ensure that when splitting, you handle the case where the split position is at the end of the word appropriately. -
Overlapping Splits:
Incorrectly processing splits might lead to missing valid combinations. Always consider both cases: when the prefix is a palindrome and when the suffix is a palindrome.
Alternative Variations
-
Duplicate Words Allowed:
If the input list can contain duplicate words, additional checks are needed to ensure that indices are distinct. -
Different Concatenation Orders:
Instead of concatenating word[i] + word[j], you might be asked to find pairs that form a palindrome when concatenated in any order. This requires a slightly different strategy.
Related Problems
-
Valid Palindrome (LeetCode 125): Check if a given string is a palindrome.
-
Palindrome Partitioning (LeetCode 131): Partition a string such that every substring is a palindrome.
GET YOUR FREE
Coding Questions Catalog
