LeetCode 336: Palindrome Pairs Solution

Master LeetCode problem 336 (Palindrome Pairs), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

336. Palindrome Pairs

Hard

Array Hash Table String Trie

Problem Explanation

Explanation:

To solve this problem, we can iterate through each word in the array and for each word, we check if there exists a valid pair that forms a palindrome when concatenated with the current word. To do this efficiently, we can utilize a hashmap to store the indices of words that have been encountered before. We then split each word into two parts and check if any valid palindrome pairs can be formed by combining these parts with other words in the array.

Algorithm:

Create a hashmap to store the indices of words.
Iterate through each word in the array.
For each word, split it into two parts: prefix and suffix.
Check if prefix or suffix is a palindrome and if the reverse of the other part exists in the hashmap.
If the conditions are satisfied, add the pair of indices to the result.
Return the list of palindrome pairs.

Time Complexity: The time complexity of this algorithm is O(n * k^2), where n is the number of words and k is the average length of a word.

Space Complexity: The space complexity is O(n * k) for the hashmap.

Solution Code

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        Map<String, Integer> wordMap = new HashMap<>();
        
        for (int i = 0; i < words.length; i++) {
            wordMap.put(words[i], i);
        }
        
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j <= words[i].length(); j++) {
                String prefix = words[i].substring(0, j);
                String suffix = words[i].substring(j);
                
                if (isPalindrome(prefix)) {
                    String reversedSuffix = new StringBuilder(suffix).reverse().toString();
                    if (wordMap.containsKey(reversedSuffix) && wordMap.get(reversedSuffix) != i) {
                        result.add(Arrays.asList(wordMap.get(reversedSuffix), i));
                    }
                }
                
                if (suffix.length() > 0 && isPalindrome(suffix)) {
                    String reversedPrefix = new StringBuilder(prefix).reverse().toString();
                    if (wordMap.containsKey(reversedPrefix) && wordMap.get(reversedPrefix) != i) {
                        result.add(Arrays.asList(i, wordMap.get(reversedPrefix)));
                    }
                }
            }
        }
        
        return result;
    }
    
    private boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 336 (Palindrome Pairs)?

This page provides optimized solutions for LeetCode problem 336 (Palindrome Pairs) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 336 (Palindrome Pairs)?

The time complexity for LeetCode 336 (Palindrome Pairs) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 336 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 336 in Java, C++, or Python.

Back to LeetCode Solutions