Palindrome Pairs

hard trie hash map string

Problem

Given a list of distinct words, return all index pairs (i, j) such that words[i] + words[j] is a palindrome.

Inputwords = ["abcd","dcba","lls","s","sssll"]

Output[[0,1],[1,0],[3,2],[2,4]]

"abcd"+"dcba", "s"+"lls", "lls"+"sssll".

words (comma-separated)

def palindrome_pairs(words):
    index = {w: i for i, w in enumerate(words)}
    def is_pal(s): return s == s[::-1]
    out = []
    for i, w in enumerate(words):
        for j in range(len(w) + 1):
            pre, suf = w[:j], w[j:]
            if is_pal(pre):
                rev = suf[::-1]
                if rev != w and rev in index: out.append([index[rev], i])
            if j != len(w) and is_pal(suf):
                rev = pre[::-1]
                if rev != w and rev in index: out.append([i, index[rev]])
    return out

function palindromePairs(words) {
  const index = new Map(); words.forEach((w, i) => index.set(w, i));
  const isPal = s => s === s.split("").reverse().join("");
  const out = [];
  for (let i = 0; i < words.length; i++) {
    const w = words[i];
    for (let j = 0; j <= w.length; j++) {
      const pre = w.slice(0, j), suf = w.slice(j);
      if (isPal(pre)) {
        const rev = suf.split("").reverse().join("");
        if (rev !== w && index.has(rev)) out.push([index.get(rev), i]);
      }
      if (j !== w.length && isPal(suf)) {
        const rev = pre.split("").reverse().join("");
        if (rev !== w && index.has(rev)) out.push([i, index.get(rev)]);
      }
    }
  }
  return out;
}

class Solution {
    boolean isPal(String s) { int i = 0, j = s.length() - 1; while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false; return true; }
    public List> palindromePairs(String[] words) {
        Map idx = new HashMap<>();
        for (int i = 0; i < words.length; i++) idx.put(words[i], i);
        List> out = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            for (int j = 0; j <= w.length(); j++) {
                String pre = w.substring(0, j), suf = w.substring(j);
                if (isPal(pre)) {
                    String rev = new StringBuilder(suf).reverse().toString();
                    if (!rev.equals(w) && idx.containsKey(rev)) out.add(Arrays.asList(idx.get(rev), i));
                }
                if (j != w.length() && isPal(suf)) {
                    String rev = new StringBuilder(pre).reverse().toString();
                    if (!rev.equals(w) && idx.containsKey(rev)) out.add(Arrays.asList(i, idx.get(rev)));
                }
            }
        }
        return out;
    }
}

class Solution {
    bool isPal(const string& s) { int i = 0, j = s.size() - 1; while (i < j) if (s[i++] != s[j--]) return false; return true; }
public:
    vector> palindromePairs(vector& words) {
        unordered_map idx;
        for (int i = 0; i < (int)words.size(); i++) idx[words[i]] = i;
        vector> out;
        for (int i = 0; i < (int)words.size(); i++) {
            const string& w = words[i];
            for (int j = 0; j <= (int)w.size(); j++) {
                string pre = w.substr(0, j), suf = w.substr(j);
                if (isPal(pre)) {
                    string rev(suf.rbegin(), suf.rend());
                    if (rev != w && idx.count(rev)) out.push_back({idx[rev], i});
                }
                if (j != (int)w.size() && isPal(suf)) {
                    string rev(pre.rbegin(), pre.rend());
                    if (rev != w && idx.count(rev)) out.push_back({i, idx[rev]});
                }
            }
        }
        return out;
    }
};

Explanation

Two words form a palindrome when glued together. The key observation is that if w is split into a prefix and a suffix, and one of those halves is already a palindrome, then we only need the reverse of the other half to exist as another word to complete the palindrome.

So we first build an index map from each word to its position for instant lookup. Then for each word w we try every split point j, giving pre = w[:j] and suf = w[j:].

Two cases. If pre is a palindrome, then reverse(suf) + w is a palindrome, so we look up reverse(suf) and pair it before w. If suf is a palindrome, then w + reverse(pre) is a palindrome, so we look up reverse(pre) and pair it after w. We guard against pairing a word with itself.

Example: ["abcd","dcba","lls","s","sssll"]. For s, the empty prefix is a palindrome and reverse("s") = "s"... more usefully, lls with palindrome suffix lets s + lls match, and abcd pairs with dcba. The output lists all such index pairs.

For each of N words we test L splits, each doing an O(L) palindrome check and lookup, giving O(N·L²).

Time: O(N · L²) Space: O(N · L)