Palindrome Pairs

Problem#

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

Examples#

words = ["abcd","dcba","lls","s","sssll"] → [[0,1],[1,0],[3,2],[2,4]].
words = ["bat","tab","cat"] → [[0,1],[1,0]].

Constraints#

1 <= words.length <= 5000, 0 <= words[i].length <= 300.

Hints#

Hint 1

If words[i] + words[j] is a palindrome, splitting at some point gives A + B where one side is a palindrome and the other side equals the reverse of the other word.

Hint 2

Index every word’s reverse. For each word, split at every point and look up the reverse of the non-palindromic side.

Approach#

Build a hash map of reversed(word) -> index. For each word, iterate split positions k = 0..len. Let left = word[0..k) and right = word[k..len). If right is palindromic, look up left in the map (some word equals reverse(left) and appended after word completes the palindrome). Symmetrically: if left is palindromic, look up right (some word equals reverse(right) prepended).

Solution#

class Solution {
    bool isPal(const string& s, int l, int r) {
        while (l < r) if (s[l++] != s[r--]) return false;
        return true;
    }
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string, int> idx;
        for (int i = 0; i < (int)words.size(); ++i) {
            string r = words[i];
            reverse(r.begin(), r.end());
            idx[r] = i;
        }
        set<pair<int,int>> dedupe;
        for (int i = 0; i < (int)words.size(); ++i) {
            const string& w = words[i];
            int n = w.size();
            for (int k = 0; k <= n; ++k) {
                // Case A: left palindrome -> look up right.
                if (isPal(w, 0, k - 1)) {
                    string suff = w.substr(k);
                    auto it = idx.find(suff);
                    if (it != idx.end() && it->second != i) dedupe.insert({it->second, i});
                }
                // Case B: right palindrome -> look up left.
                if (k != n && isPal(w, k, n - 1)) {
                    string pref = w.substr(0, k);
                    auto it = idx.find(pref);
                    if (it != idx.end() && it->second != i) dedupe.insert({i, it->second});
                }
            }
        }
        return {dedupe.begin(), dedupe.end()};
    }
};

func palindromePairs(words []string) [][]int {
    isPal := func(s string, l, r int) bool {
        for l < r {
            if s[l] != s[r] {
                return false
            }
            l++
            r--
        }
        return true
    }
    idx := make(map[string]int)
    for i, w := range words {
        r := []byte(w)
        for l, rr := 0, len(r)-1; l < rr; l, rr = l+1, rr-1 {
            r[l], r[rr] = r[rr], r[l]
        }
        idx[string(r)] = i
    }
    dedupe := make(map[[2]int]bool)
    for i, w := range words {
        n := len(w)
        for k := 0; k <= n; k++ {
            // Case A: left palindrome -> look up right.
            if isPal(w, 0, k-1) {
                suff := w[k:]
                if j, ok := idx[suff]; ok && j != i {
                    dedupe[[2]int{j, i}] = true
                }
            }
            // Case B: right palindrome -> look up left.
            if k != n && isPal(w, k, n-1) {
                pref := w[:k]
                if j, ok := idx[pref]; ok && j != i {
                    dedupe[[2]int{i, j}] = true
                }
            }
        }
    }
    ans := make([][]int, 0, len(dedupe))
    for p := range dedupe {
        ans = append(ans, []int{p[0], p[1]})
    }
    return ans
}

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def is_pal(s: str, l: int, r: int) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        idx = {w[::-1]: i for i, w in enumerate(words)}
        dedupe = set()
        for i, w in enumerate(words):
            n = len(w)
            for k in range(n + 1):
                # Case A: left palindrome -> look up right.
                if is_pal(w, 0, k - 1):
                    suff = w[k:]
                    if suff in idx and idx[suff] != i:
                        dedupe.add((idx[suff], i))
                # Case B: right palindrome -> look up left.
                if k != n and is_pal(w, k, n - 1):
                    pref = w[:k]
                    if pref in idx and idx[pref] != i:
                        dedupe.add((i, idx[pref]))
        return [list(p) for p in dedupe]

function palindromePairs(words) {
    const isPal = (s, l, r) => {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    };
    const idx = new Map();
    for (let i = 0; i < words.length; i++) {
        idx.set(words[i].split('').reverse().join(''), i);
    }
    const dedupe = new Set();
    for (let i = 0; i < words.length; i++) {
        const w = words[i];
        const n = w.length;
        for (let k = 0; k <= n; k++) {
            // Case A: left palindrome -> look up right.
            if (isPal(w, 0, k - 1)) {
                const suff = w.slice(k);
                if (idx.has(suff) && idx.get(suff) !== i) {
                    dedupe.add(`${idx.get(suff)},${i}`);
                }
            }
            // Case B: right palindrome -> look up left.
            if (k !== n && isPal(w, k, n - 1)) {
                const pref = w.slice(0, k);
                if (idx.has(pref) && idx.get(pref) !== i) {
                    dedupe.add(`${i},${idx.get(pref)}`);
                }
            }
        }
    }
    return [...dedupe].map(s => s.split(',').map(Number));
}

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String, Integer> idx = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            idx.put(new StringBuilder(words[i]).reverse().toString(), i);
        }
        Set<List<Integer>> dedupe = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            int n = w.length();
            for (int k = 0; k <= n; k++) {
                // Case A: left palindrome -> look up right.
                if (isPal(w, 0, k - 1)) {
                    String suff = w.substring(k);
                    Integer j = idx.get(suff);
                    if (j != null && j != i) dedupe.add(Arrays.asList(j, i));
                }
                // Case B: right palindrome -> look up left.
                if (k != n && isPal(w, k, n - 1)) {
                    String pref = w.substring(0, k);
                    Integer j = idx.get(pref);
                    if (j != null && j != i) dedupe.add(Arrays.asList(i, j));
                }
            }
        }
        return new ArrayList<>(dedupe);
    }

    private boolean isPal(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

function palindromePairs(words: string[]): number[][] {
    const isPal = (s: string, l: number, r: number): boolean => {
        while (l < r) {
            if (s[l] !== s[r]) return false;
            l++;
            r--;
        }
        return true;
    };
    const idx: Map<string, number> = new Map();
    for (let i = 0; i < words.length; i++) {
        idx.set(words[i].split('').reverse().join(''), i);
    }
    const dedupe: Set<string> = new Set();
    for (let i = 0; i < words.length; i++) {
        const w = words[i];
        const n = w.length;
        for (let k = 0; k <= n; k++) {
            // Case A: left palindrome -> look up right.
            if (isPal(w, 0, k - 1)) {
                const suff = w.slice(k);
                if (idx.has(suff) && idx.get(suff) !== i) {
                    dedupe.add(`${idx.get(suff)},${i}`);
                }
            }
            // Case B: right palindrome -> look up left.
            if (k !== n && isPal(w, k, n - 1)) {
                const pref = w.slice(0, k);
                if (idx.has(pref) && idx.get(pref) !== i) {
                    dedupe.add(`${i},${idx.get(pref)}`);
                }
            }
        }
    }
    return [...dedupe].map(s => s.split(',').map(Number));
}

Editorial#

Every palindromic concatenation splits at exactly one point into “palindrome half plus reverse-match half”. Iterating splits covers all cases including empty strings (the empty string is a palindrome, so it pairs with every palindromic word in both orders). The set dedupes the case where both halves are palindromic and both cases A/B insert the same pair.

Complexity#

Time: O(N * L^2) — N words, L splits each, each split’s palindrome check is O(L).
Space: O(N * L) for the reverse map.

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#