DevExCode

LeetCode 336: Palindrome Pairs

ArrayHash TableStringTrie

Problem Description

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:

  1. Create a hashmap to store the indices of words.
  2. Iterate through each word in the array.
  3. For each word, split it into two parts: prefix and suffix.
  4. Check if prefix or suffix is a palindrome and if the reverse of the other part exists in the hashmap.
  5. If the conditions are satisfied, add the pair of indices to the result.
  6. 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.

:

View on LeetCode

Solutions

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;
    }
}

Related LeetCode Problems

Previous ProblemNext Problem

Loading editor...