336. Palindrome Pairs

Question

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:

Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

Thinking:

• Method 1: Brutal force TLE

    class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            int len = words.length;
            List<List<Integer>> res = new ArrayList<>();
            for(int i = 0; i < len; i++){
                for(int j = 0; j < len; j++){
                    if(i == j) continue;
                    if(isPalindrome(words[i] + words[j])){
                        List<Integer> temp = new ArrayList<>();
                        temp.add(i);
                        temp.add(j);
                        res.add(temp);
                    }
                }
            }
            return res;
        }
        private boolean isPalindrome(String s){
            int left = 0, right = s.length() - 1;
            char[] arr = s.toCharArray();
            while(left < right){
                if(arr[left++] != arr[right--])
                    return false;
            }
            return true;
        }
    }
  

• Method 2: HashMap O(N * K^2)

    class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> res = new ArrayList<>();
            if(words == null || words.length < 2) return res;
            Map<String, Integer> map = new HashMap<>();
            for(int i = 0; i < words.length; i++){  // O(N)
                map.put(words[i], i);
            }
            for(int i = 0; i < words.length; i++){  // O(N * k)
                for(int j = 0; j <= words[i].length(); j++){
                    String first = words[i].substring(0, j);
                    String second = words[i].substring(j);
                    if(isPalindrome(first)){    // O(k)
                        //first is palindrome, check if we have reverse of second
                        String reverse = new StringBuilder(second).reverse().toString();
                        if(map.containsKey(reverse) && map.get(reverse) != i){
                            List<Integer> temp = new ArrayList<>();
                            temp.add(map.get(reverse));
                            temp.add(i);
                            res.add(temp);
                        }
                    }
                    if(second.length() != 0 && isPalindrome(second)){   // O(k)
                        String reverse = new StringBuilder(first).reverse().toString();
                        if(map.containsKey(reverse) && map.get(reverse) != i){
                            List<Integer> temp = new ArrayList<>();
                            temp.add(i);
                            temp.add(map.get(reverse));
                            res.add(temp);
                        }
                    }
                }
            }
            return res;
        }
        private boolean isPalindrome(String s){
            int left = 0, right = s.length() - 1;
            char[] arr = s.toCharArray();
            while(left < right){
                if(arr[left++] != arr[right--])
                    return false;
            }
            return true;
        }
    }
  

• Method 3: Tire Tree

    class Solution {
        private static class Node{
            Node[] childs;
            boolean isLeaf;
            int index;
            public Node(){
                this.childs = new Node[26];
            }
        }
        private Node root;
        private void insert(String s, int index){
            char[] arr = s.toCharArray();
            Node temp = root;
            for(int i = 0; i < arr.length; i++){
                if(temp.childs[arr[i] - 'a'] == null){
                    temp.childs[arr[i] - 'a'] = new Node();
                }
                temp = temp.childs[arr[i] - 'a'];
            }
            temp.isLeaf = true;
            temp.index = index;
        }
        private Node contains(String s){
            char[] arr = s.toCharArray();
            Node temp = root;
            for(int i = 0; i < arr.length; i++){
                if(temp.childs[arr[i] - 'a'] == null) return null;
                temp = temp.childs[arr[i] - 'a'];
            }
            return temp;
        }
        public List<List<Integer>> palindromePairs(String[] words) {
            this.root = new Node();
            for(int i = 0; i < words.length; i++){
                insert(words[i], i);
            }
            List<List<Integer>> result = new ArrayList<>();
            for(int i = 0; i < words.length; i++){
                for(int j = 0; j <= words[i].length(); j++){
                    String first = words[i].substring(0, j);
                    String second = words[i].substring(j);
                    if(isPalindrome(first)){
                        String reverse = new StringBuilder(second).reverse().toString();
                        Node temp = contains(reverse);
                        if(temp != null && temp.isLeaf && temp.index != i){
                            result.add(Arrays.asList(temp.index, i));
                        }
                    }
                    if(second.length() != 0 && isPalindrome(second)){
                        String reverse = new StringBuilder(first).reverse().toString();
                        Node temp = contains(reverse);
                        if(temp != null && temp.isLeaf && temp.index != i){
                            result.add(Arrays.asList(i, temp.index));
                        }
                    }
                }
            }
            return result;
        }
        private boolean isPalindrome(String s){
            int l = 0, r = s.length() - 1;
            while(l < r){
                if(s.charAt(l++) != s.charAt(r--)) return false;
            }
            return true;
        }
    }