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<>();
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/palindrome-pairs/
    // Time: O(N * L^2)
    // Space: O(NL)
    // Ref: https://leetcode.com/problems/palindrome-pairs/discuss/79195/O(n-*-k2)-java-solution-with-Trie-structure
    struct TrieNode {
        TrieNode *next[26] = {};
        int index = -1;
        vector<int> palindromeIndexes;
    };
    class Solution {
        TrieNode root; // Suffix trie
        void add(string &s, int i) {
            auto node = &root;
            for (int j = s.size() - 1; j >= 0; --j) {
                if (isPalindrome(s, 0, j)) node->palindromeIndexes.push_back(i); // A[i]'s prefix forms a palindrome
                int c = s[j] - 'a';
                if (!node->next[c]) node->next[c] = new TrieNode();
                node = node->next[c];
            }
            node->index = i;
            node->palindromeIndexes.push_back(i); // A[i]'s prefix is empty string here, which is a palindrome.
        }
        bool isPalindrome(string &s, int i, int j) {
            while (i < j && s[i] == s[j]) ++i, --j;
            return i >= j;
        }
    public:
        vector<vector<int>> palindromePairs(vector<string>& A) {
            int N = A.size();
            for (int i = 0; i < N; ++i) add(A[i], i);
            vector<vector<int>> ans;
            for (int i = 0; i < N; ++i) {
                auto s = A[i];
                auto node = &root;
                for (int j = 0; j < s.size() && node; ++j) {
                    if (node->index != -1 && node->index != i && isPalindrome(s, j, s.size() - 1)) ans.push_back({ i, node->index }); // A[i]'s prefix matches this word and A[i]'s suffix forms a palindrome
                    node = node->next[s[j] - 'a'];
                }
                if (!node) continue;
                for (int j : node->palindromeIndexes) { // A[i] is exhausted in the matching above. If a word whose prefix is palindrome after matching its suffix with A[i], then this is also a valid pair
                    if (i != j) ans.push_back({ i, j });
                }
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def palindromePairs(self, words):
        """
        :type words: List[str]
        :rtype: List[List[int]]
        """
        ans = []
        d = {}
        for i, word in enumerate(words):
          d[word] = i
    
        for i, word in enumerate(words):
          if word == "":
            ans.extend([(i, j) for j in range(len(words)) if i != j and words[j] == words[j][::-1]])
            continue
          for j in range(len(word)):
            left = word[:j]
            right = word[j:]
            if right == right[::-1] and left[::-1] in d and d[left[::-1]] != i:
              ans.append((i, d[left[::-1]]))
            if left == left[::-1] and right[::-1] in d and d[right[::-1]] != i:
              ans.append((d[right[::-1]], i))
        return ans
    
    

All Problems

All Solutions