Palindrome Pairs — HashMap + Palindrome Check

Problem 204 · Palindrome Pairs

Difficulty: Hard · Pattern: HashMap + Palindrome Split

Given a list of unique words, find all pairs (i,j) where words[i]+words[j] is a palindrome.

Intuition

For each word, try all possible splits into (prefix, suffix). If prefix is a palindrome and reverse(suffix) is in the map → valid pair. If suffix is a palindrome and reverse(prefix) is in the map → valid pair. Handle empty string edge cases.

Solutions

# Python
def palindromePairs(words):
    def is_pal(s, l, r):
        while l < r:
            if s[l] != s[r]: return False
            l += 1; r -= 1
        return True

    word_map = {w: i for i, w in enumerate(words)}
    res = []

    for i, word in enumerate(words):
        n = len(word)
        for j in range(n + 1):
            # Case 1: prefix[0..j-1] is palindrome, look for reverse(suffix)
            if is_pal(word, 0, j-1):
                rev_suf = word[j:][::-1]
                if rev_suf in word_map and word_map[rev_suf] != i:
                    res.append([word_map[rev_suf], i])
            # Case 2: suffix[j..n-1] is palindrome, look for reverse(prefix)
            if j < n and is_pal(word, j, n-1):
                rev_pre = word[:j][::-1]
                if rev_pre in word_map and word_map[rev_pre] != i:
                    res.append([i, word_map[rev_pre]])
    return res

// Java
public List<List<Integer>> palindromePairs(String[] words) {
    Map<String,Integer> map = new HashMap<>();
    for (int i = 0; i < words.length; i++)
        map.put(new StringBuilder(words[i]).reverse().toString(), i);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < words.length; i++) {
        String w = words[i]; int n = w.length();
        for (int j = 0; j <= n; j++) {
            // prefix palindrome
            if (isPal(w, 0, j-1)) {
                String suf = w.substring(j);
                if (map.containsKey(suf) && map.get(suf) != i)
                    res.add(Arrays.asList(map.get(suf), i));
            }
            // suffix palindrome
            if (j < n && isPal(w, j, n-1)) {
                String pre = w.substring(0, j);
                if (map.containsKey(pre) && map.get(pre) != i)
                    res.add(Arrays.asList(i, map.get(pre)));
            }
        }
    }
    return res;
}
boolean isPal(String s, int l, int r) {
    while (l<r) if (s.charAt(l++)!=s.charAt(r--)) return false;
    return true;
}

Complexity

Time: O(n * k²) where k = average word length
Space: O(n * k)