Question

Formatted question description: https://leetcode.ca/all/336.html

 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:

 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"]

 @tag-trie

Algorithm

step1: put the reverse order of the words into a map

step 2 & 3: check the prefix of each word.

It can form a palindrome iff

  • prefix in the map AND
  • rest substring is a palindrome.

e.g. “abll”, if the prefix is ab, and the map contains a “ab”, then we can form a palindrome which is abllba

Check the postfix of each word. The word can form a palindrome iff

  • postfix is in the map AND
  • the rest of prefix is a palindrome e.g. “llab”, where the postfix is ab, if the map cotnains a “ab”, then we can form a palindrome of ballab

Code

Java

import java.util.*;

public class Palindrome_Pairs {

    public class Solution {

        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> result = new ArrayList<>();

            if (words == null || words.length == 0) {
                return result;
            }

            // step1: put the reverse order of the words into a map
            Map<String, Integer> map = new HashMap<>();
            for (int i = 0; i < words.length; i++) {
                String reversedWord = reverse(words[i]);
                map.put(reversedWord, i);
            }

            // step 2 & 3: check the prefix of each word.
            // It can form a palindrome iff
            //      prefix in the map AND
            //      rest substring is a palindrome.
            // e.g. "abll", if the prefix is ab, and the map contains a "ab", then
            //      we can form a palindrome which is abllba

            // check the postfix of each word.
            // The word can form a palindrome iff
            //      postfix is in the map AND
            //      the rest of prefix is a palindrome
            // e.g. "llab", where the postfix is ab, if the map cotnains a "ab", then
            //      we can form a palindrome of ballab
            for (int i = 0; i < words.length; i++) {
                String word = words[i];

                // get prefix of each word
                for (int j = 0; j <= word.length(); j++) {
                    String prefix = word.substring(0, j);
                    String rest = word.substring(j);
                    // !=i, not the same word itself
                    if (map.containsKey(prefix) && isPalindrome(rest) && map.get(prefix) != i) {
                        List<Integer> curr = new ArrayList<>();
                        curr.add(i);
                        curr.add(map.get(prefix));
                        result.add(curr);
                    }
                }

                // get postfix of each word
                // substring to is exclusive
                for (int j = word.length(); j > 0; j--) {
                    String postfix = word.substring(j);
                    String rest = word.substring(0, j);
                    if (map.containsKey(postfix) && isPalindrome(rest) &&
                        map.get(postfix) != i) {
                        List<Integer> curr = new ArrayList<>();
                        curr.add(map.get(postfix));
                        curr.add(i);
                        result.add(curr);
                    }
                }
            }

            return result;
        }

        private String reverse(String s) {
            if (s == null || s.length() == 0) {
                return "";
            }

            char[] array = s.toCharArray();
            int start = 0;
            int end = array.length - 1;

            while (start < end) {
                swap(start, end, array);
                start++;
                end--;
            }

            return new String(array);
        }

        private void swap(int start, int end, char[] array) {
            char temp = array[start];
            array[start] = array[end];
            array[end] = temp;
        }

        private boolean isPalindrome(String s) {
            if (s == null || s.length() == 0) {
                return true;
            }

            int start = 0;
            int end = s.length() - 1;

            while (start < end) {
                if (s.charAt(start) != s.charAt(end)) {
                    return false;
                }
                start++;
                end--;
            }

            return true;
        }
    }

    // O(n * k^2)
    // @todo
    class Solution_Trie {
        public List<List<Integer>> palindromePairs(String[] words) {
            List<List<Integer>> res = new ArrayList<>();

            TrieNode root = new TrieNode();

            for (int i = 0; i < words.length; i++) {
                addWord(root, words[i], i);
            }

            for (int i = 0; i < words.length; i++) {
                search(words, i, root, res);
            }

            return res;
        }

        private void addWord(TrieNode root, String word, int index) {
            for (int i = word.length() - 1; i >= 0; i--) {
                int j = word.charAt(i) - 'a';

                if (root.next[j] == null) {
                    root.next[j] = new TrieNode();
                }

                if (isPalindrome(word, 0, i)) {
                    root.list.add(index);
                }

                root = root.next[j];
            }

            root.list.add(index);
            root.index = index;
        }

        private void search(String[] words, int i, TrieNode root, List<List<Integer>> res) {
            for (int j = 0; j < words[i].length(); j++) {
                if (root.index >= 0 && root.index != i && isPalindrome(words[i], j, words[i].length() - 1)) {
                    res.add(Arrays.asList(i, root.index));
                }

                root = root.next[words[i].charAt(j) - 'a'];
                if (root == null) return;
            }

            for (int j : root.list) {
                if (i == j) continue;
                res.add(Arrays.asList(i, j));
            }
        }

        private boolean isPalindrome(String word, int i, int j) {
            while (i < j) {
                if (word.charAt(i++) != word.charAt(j--)) return false;
            }

            return true;
        }

    }

    class TrieNode {
        TrieNode[] next;
        int index;
        List<Integer> list;

        TrieNode() {
            next = new TrieNode[26];
            index = -1;
            list = new ArrayList<>();
        }
    }

}

All Problems

All Solutions