Palindrome Pairs

Given a list of unique words, find all pairs [i,j] such that words[i]+words[j] is a palindrome.

Example 1

Input: ["abcd","dcba","lls","s","sssll"] → Output: [[0,1],[1,0],[3,2],[2,4]]

Example 2

Input: ["bat","tab","cat"] → Output: [[0,1],[1,0]]

Solution Approach

Use a HashMap. For each word, check its prefixes and suffixes: if prefix is palindrome, reversed suffix is a match; if suffix is palindrome, reversed prefix is a match.

Build Map: word -> index.
For each word w and each split (prefix, suffix):
If prefix is palindrome and reversed(suffix) in map: add pair.
If suffix is palindrome and reversed(prefix) in map: add pair.
Handle empty string case.

Java

import java.util.*;

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) map.put(words[i], i);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String w = words[i];
            for (int j = 0; j <= w.length(); j++) {
                String p = w.substring(0, j), s = w.substring(j);
                if (isPalin(p)) {
                    String rev = new StringBuilder(s).reverse().toString();
                    if (map.containsKey(rev) && map.get(rev) != i)
                        res.add(Arrays.asList(map.get(rev), i));
                }
                if (s.length() > 0 && isPalin(s)) {
                    String rev = new StringBuilder(p).reverse().toString();
                    if (map.containsKey(rev) && map.get(rev) != i)
                        res.add(Arrays.asList(i, map.get(rev)));
                }
            }
        }
        return res;
    }
    private boolean isPalin(String s) {
        int l=0,r=s.length()-1;
        while(l<r) if(s.charAt(l++)!=s.charAt(r--)) return false;
        return true;
    }
}

Time Complexity: O(N * L^2)
Space Complexity: O(N * L)