336. Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Given words = [“bat”, “tab”, “cat”]
Return [[0, 1], [1, 0]]
The palindromes are [“battab”, “tabbat”]
Example 2:
Given words = [“abcd”, “dcba”, “lls”, “s”, “sssll”]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are [“dcbaabcd”, “abcddcba”, “slls”, “llssssll”]

O(n k^2 ) time O(n) space HashMap solution

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new LinkedList<>();
        if (words == null || words.length == 0) {
            return result;
        }
        HashMap<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++) {
            for (int j = 0; j <= words[i].length(); j++) {
                String left = words[i].substring(0, j);
                String right = words[i].substring(j);
                if (isPalindrome(left)) {
                    String rightRev = new StringBuilder(right).reverse().toString();
                    if (map.getOrDefault(rightRev, i) != i) {
                        result.add(Arrays.asList(map.get(rightRev), i));
                    }
                }
                if (isPalindrome(right) && right.length() != 0) {
                    String leftRev = new StringBuilder(left).reverse().toString();
                    if (map.getOrDefault(leftRev, i) != i) {
                        result.add(Arrays.asList(map.get(leftRev), i));
                    }
                }
            }
        }
        return result;
    }
    
    public boolean isPalindrome(String word) {
        int left = 0, right = word.length() - 1;
        while (left <= right) {
            if (word.charAt(left) != word.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

O(n k^2 ) time O(26k) space Trie solution

public class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> result = new LinkedList<>();
        if (words == null || words.length == 0) {
            return result;
        }
        TrieNode root = new TrieNode();
        for (int i = 0; i < words.length; i++) {
            addWord(words[i], root, i);
        }
        for (int i = 0; i < words.length; i++) {
            searchWord(words[i], root, i, result);
        }
        return result;
    }
    
    public void addWord(String word, TrieNode root, int index) {
        for (int i = word.length() - 1; i >= 0; i--) {
            if (root.next[word.charAt(i) - 'a'] == null) {
                root.next[word.charAt(i) - 'a'] = new TrieNode();
            }
            if (isPalindrome(word, 0, i)) {
                root.list.add(index);
            }
            root = root.next[word.charAt(i) - 'a'];
        }
        root.index = index;
        root.list.add(index);
    }
    
    public void searchWord(String word, TrieNode root, int index, List<List<Integer>> result) {
        for (int i = 0; i < word.length(); i++) {
            if (root.index >= 0 && root.index != index && isPalindrome(word, i, word.length() - 1)) {
                result.add(Arrays.asList(index, root.index));
            }
            
            root = root.next[word.charAt(i) - 'a'];
            if (root == null) {
                return;
            }
        }
        for (int j : root.list) {
            if (j != index) {
                result.add(Arrays.asList(index, j));
            }
        }
    }
    
    public class TrieNode {
        TrieNode[] next;
        int index;
        List<Integer> list;
        
        public TrieNode() {
            next = new TrieNode[26];
            index = -1;
            list = new LinkedList<>();
        }
    }
    
    public boolean isPalindrome(String word, int start, int end) {
        while (start < end) {
            if (word.charAt(start++) != word.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}