Palindrome Pairs

We can optimize the brute-force approach by avoiding the inner loop that iterates through all other words. Instead, for each word w1, we can deduce what its partner word w2 must look like. If w1 + w2 is a palindrome, w2 must be related to the reverse of w1. We can pre-process the words into a HashMap for quick lookups.

There are three main scenarios for a pair (w1, w2):

1. len(w1) == len(w2): w2 must be the reverse of w1.
2. len(w1) > len(w2): w1 must be of the form P + S, where S is the reverse of w2 and P is a palindrome.
3. len(w1) < len(w2): w2 must be of the form S + P, where S is the reverse of w1 and P is a palindrome.

We can iterate through each word and all its possible splits into a prefix and a suffix. If one part is a palindrome, we look for the reverse of the other part in the map.

• Create a HashMap to store each word and its index. This allows for O(1) average time lookups.
• Handle the edge case of an empty string. If "" exists in words, find its index. Then, iterate through all other words; if a word is a palindrome, it can form a pair with the empty string in both orders.
• Iterate through each word w at index i in the words array.
• For each word w, iterate through all possible split points j from 0 to w.length().
• Split w into prefix = w.substring(0, j) and suffix = w.substring(j).
• Case 1: Check if the prefix is a palindrome. If it is, reverse the suffix to get reversedSuffix. Look for reversedSuffix in the HashMap. If it exists at an index k different from i, then (k, i) is a palindrome pair (words[k] + words[i] forms a palindrome).
• Case 2: Check if the suffix is a palindrome. If it is, reverse the prefix to get reversedPrefix. Look for reversedPrefix in the HashMap. If it exists at an index k different from i, then (i, k) is a palindrome pair. Note: When j=0, the prefix is empty, and this case becomes checking for the reverse of the whole word. To avoid duplicates when the suffix is empty (j = w.length()), we can add a condition suffix.length() > 0 or use a Set for the results.

This approach improves upon brute force by intelligently searching for the second word in a pair. By pre-populating a HashMap with all words and their indices, we can quickly check for the existence of a required word (e.g., the reverse of a suffix). The main logic involves iterating through each word and, for each word, iterating through all possible split points. This creates a prefix and a suffix. We check if either part is a palindrome. If the prefix is a palindrome, we need a word that is the reverse of the suffix to place before our current word. If the suffix is a palindrome, we need a word that is the reverse of the prefix to place after our current word.

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i], i);
        }

        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);

                // Case 1: prefix is a palindrome, look for reversed suffix
                if (isPalindrome(prefix)) {
                    String reversedSuffix = new StringBuilder(suffix).reverse().toString();
                    if (map.containsKey(reversedSuffix) && map.get(reversedSuffix) != i) {
                        result.add(Arrays.asList(map.get(reversedSuffix), i));
                    }
                }

                // Case 2: suffix is a palindrome, look for reversed prefix
                // suffix.length() != 0 to avoid duplicates when word is a palindrome
                // (e.g. "aba", prefix="aba", suffix=""). This is handled by Case 1 when j=0.
                if (isPalindrome(suffix) && suffix.length() != 0) {
                    String reversedPrefix = new StringBuilder(prefix).reverse().toString();
                    if (map.containsKey(reversedPrefix) && map.get(reversedPrefix) != i) {
                        result.add(Arrays.asList(i, map.get(reversedPrefix)));
                    }
                }
            }
        }
        return result;
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}