Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

336. Palindrome Pairs - Leetcode Solution

Code Implementation

class Solution:
    def palindromePairs(self, words):
        def is_palindrome(check):
            return check == check[::-1]
        
        word_to_index = {w: i for i, w in enumerate(words)}
        res = []
        for i, word in enumerate(words):
            for j in range(len(word) + 1):
                prefix = word[:j]
                suffix = word[j:]
                if is_palindrome(prefix):
                    back = suffix[::-1]
                    if back != word and back in word_to_index:
                        res.append([word_to_index[back], i])
                if j != len(word) and is_palindrome(suffix):
                    back = prefix[::-1]
                    if back != word and back in word_to_index:
                        res.append([i, word_to_index[back]])
        return res
      
class Solution {
public:
    bool isPalindrome(const string& s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l++] != s[r--]) return false;
        }
        return true;
    }
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string, int> wordToIndex;
        for (int i = 0; i < words.size(); ++i) {
            wordToIndex[words[i]] = i;
        }
        vector<vector<int>> res;
        for (int i = 0; i < words.size(); ++i) {
            string word = words[i];
            for (int j = 0; j <= word.size(); ++j) {
                string prefix = word.substr(0, j);
                string suffix = word.substr(j);
                if (isPalindrome(prefix)) {
                    string back = string(suffix.rbegin(), suffix.rend());
                    if (wordToIndex.count(back) && wordToIndex[back] != i) {
                        res.push_back({wordToIndex[back], i});
                    }
                }
                if (j != word.size() && isPalindrome(suffix)) {
                    string back = string(prefix.rbegin(), prefix.rend());
                    if (wordToIndex.count(back) && wordToIndex[back] != i) {
                        res.push_back({i, wordToIndex[back]});
                    }
                }
            }
        }
        return res;
    }
};
      
class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> wordToIndex = new HashMap<>();
        for (int i = 0; i < words.length; ++i) {
            wordToIndex.put(words[i], i);
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < words.length; ++i) {
            String word = words[i];
            for (int j = 0; j <= word.length(); ++j) {
                String prefix = word.substring(0, j);
                String suffix = word.substring(j);
                if (isPalindrome(prefix)) {
                    String back = new StringBuilder(suffix).reverse().toString();
                    if (wordToIndex.containsKey(back) && wordToIndex.get(back) != i) {
                        res.add(Arrays.asList(wordToIndex.get(back), i));
                    }
                }
                if (j != word.length() && isPalindrome(suffix)) {
                    String back = new StringBuilder(prefix).reverse().toString();
                    if (wordToIndex.containsKey(back) && wordToIndex.get(back) != i) {
                        res.add(Arrays.asList(i, wordToIndex.get(back)));
                    }
                }
            }
        }
        return res;
    }
    private boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }
}
      
var palindromePairs = function(words) {
    const wordToIndex = {};
    for (let i = 0; i < words.length; ++i) {
        wordToIndex[words[i]] = i;
    }
    const isPalindrome = s => s === s.split('').reverse().join('');
    const res = [];
    for (let i = 0; i < words.length; ++i) {
        let word = words[i];
        for (let j = 0; j <= word.length; ++j) {
            let prefix = word.substring(0, j);
            let suffix = word.substring(j);
            if (isPalindrome(prefix)) {
                let back = suffix.split('').reverse().join('');
                if (wordToIndex.hasOwnProperty(back) && wordToIndex[back] !== i) {
                    res.push([wordToIndex[back], i]);
                }
            }
            if (j !== word.length && isPalindrome(suffix)) {
                let back = prefix.split('').reverse().join('');
                if (wordToIndex.hasOwnProperty(back) && wordToIndex[back] !== i) {
                    res.push([i, wordToIndex[back]]);
                }
            }
        }
    }
    return res;
};

Problem Description

Given a list of unique words in a string array words, find all unique pairs of indices (i, j) such that the concatenation of words[i] + words[j] is a palindrome. Each word can only be used at its own index, and pairs must use different indices. Return all such index pairs in any order.

Key Constraints:
  • Each pair must use two different indices (i ≠ j).
  • Each input word is unique.
  • There may be multiple valid pairs, or none at all.
  • Return all valid pairs; order does not matter.

Thought Process

When first approaching this problem, it is tempting to try every possible pair of words, concatenate them, and check if the result is a palindrome. This brute-force method is straightforward, but becomes inefficient as the number of words grows.

To optimize, we notice that checking all pairs does a lot of repeated work. For example, we may check the same substring multiple times. Instead, we can use properties of palindromes: if a word's prefix (or suffix) is a palindrome, and the remaining part matches another word in reverse, then together they form a palindrome. This insight allows us to use a hash map for quick lookups, reducing unnecessary repeated checks.

The key is to break each word into all possible prefix and suffix splits, and for each, check if the other half’s reverse exists elsewhere in the list.

Solution Approach

The solution uses a hash map and palindrome properties to efficiently find all palindrome pairs.
  • Step 1: Build a hash map (word_to_index) mapping each word to its index for O(1) lookups.
  • Step 2: For each word, split it at every possible position (including before the first character and after the last), creating a prefix and suffix.
  • Step 3: For each split:
    • If the prefix is a palindrome, check if the reversed suffix exists as another word. If so, the pair (reversed_suffix, current word) forms a palindrome.
    • If the suffix is a palindrome (and not the whole word), check if the reversed prefix exists as another word. If so, the pair (current word, reversed_prefix) forms a palindrome.
  • Step 4: Collect all valid pairs, avoiding duplicates and self-pairings (where i == j).
Justification: We use a hash map for fast lookups, and check palindromes only on substrings, which is much faster than checking all concatenations. By considering every possible split, we ensure all valid palindrome pairs are found.

Example Walkthrough

Sample Input:
words = ["abcd", "dcba", "lls", "s", "sssll"]

Let's walk through "abcd":
  • Splits: '', 'abcd' | 'a','bcd' | 'ab','cd' | 'abc','d' | 'abcd',''
  • For split '', 'abcd': '' is a palindrome, look for 'dcba' (reverse of 'abcd'). Found at index 1. So (1,0) is valid.
  • For split 'abcd','': '' is a palindrome, look for 'dcba' (reverse of 'abcd'). Already covered.
  • Other splits: neither 'a','bcd' nor 'ab','cd' nor 'abc','d' have both sides as palindromes and a matching reverse elsewhere.
Now, "lls":
  • Split 'll','s': 'll' is a palindrome, 's' reversed is 's', which is at index 3. So (3,2) is valid.
  • Split 'lls','': '' is a palindrome, 'sll' reversed is 'lls', which is not in the list.
This process repeats for each word, yielding pairs: [1,0], [0,1], [3,2], [2,4].

Time and Space Complexity

Brute-force:
  • Time: O(N^2 * K), where N is number of words and K is average word length (for concatenation and palindrome check).
  • Space: O(1) extra (ignoring output).
Optimized Approach:
  • Time: O(N * K^2), since for each word (N), we check all splits (up to K), and for each split, check palindrome (up to K).
  • Space: O(N*K) for the hash map and output.
The optimized method is much faster for large inputs.

Summary

This problem is a classic example of using hash maps and palindrome properties to optimize what would otherwise be a brute-force search. By considering all possible splits of each word and leveraging quick lookups for reversed substrings, we efficiently discover all palindrome pairs. The elegance lies in reducing redundant work and focusing only on promising candidates, making the solution both fast and clean.