Question

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

You are given a 0-indexed array of unique strings words.

A palindrome pair is a pair of integers (i, j) such that:

0 <= i, j < words.length,
i != j, and
words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return an array of all the palindrome pairs of words.

Example 1:

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

Example 2:

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

Example 3:

Input: words = ["a",""]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["a","a"]

Constraints:

1 <= words.length <= 5000
0 <= words[i].length <= 300
words[i] consists of lowercase English letters.

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

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

}

############

class Solution {
    private static final int BASE = 131;
    private static final long[] MUL = new long[310];
    private static final int MOD = (int) 1e9 + 7;
    static {
        MUL[0] = 1;
        for (int i = 1; i < MUL.length; ++i) {
            MUL[i] = (MUL[i - 1] * BASE) % MOD;
        }
    }
    public List<List<Integer>> palindromePairs(String[] words) {
        int n = words.length;
        long[] prefix = new long[n];
        long[] suffix = new long[n];
        for (int i = 0; i < n; ++i) {
            String word = words[i];
            int m = word.length();
            for (int j = 0; j < m; ++j) {
                int t = word.charAt(j) - 'a' + 1;
                int s = word.charAt(m - j - 1) - 'a' + 1;
                prefix[i] = (prefix[i] * BASE) % MOD + t;
                suffix[i] = (suffix[i] * BASE) % MOD + s;
            }
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (check(i, j, words[j].length(), words[i].length(), prefix, suffix)) {
                    ans.add(Arrays.asList(i, j));
                }
                if (check(j, i, words[i].length(), words[j].length(), prefix, suffix)) {
                    ans.add(Arrays.asList(j, i));
                }
            }
        }
        return ans;
    }

    private boolean check(int i, int j, int n, int m, long[] prefix, long[] suffix) {
        long t = ((prefix[i] * MUL[n]) % MOD + prefix[j]) % MOD;
        long s = ((suffix[j] * MUL[m]) % MOD + suffix[i]) % MOD;
        return t == s;
    }
}

// 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:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        d = {w: i for i, w in enumerate(words)}
        ans = []
        for i, w in enumerate(words):
            for j in range(len(w) + 1):
                a, b = w[:j], w[j:]
                ra, rb = a[::-1], b[::-1]
                if ra in d and d[ra] != i and b == rb:
                    ans.append([i, d[ra]])
                if j and rb in d and d[rb] != i and a == ra:
                    ans.append([d[rb], i])
        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

func palindromePairs(words []string) [][]int {
	base := 131
	mod := int(1e9) + 7
	mul := make([]int, 310)
	mul[0] = 1
	for i := 1; i < len(mul); i++ {
		mul[i] = (mul[i-1] * base) % mod
	}
	n := len(words)
	prefix := make([]int, n)
	suffix := make([]int, n)
	for i, word := range words {
		m := len(word)
		for j, c := range word {
			t := int(c-'a') + 1
			s := int(word[m-j-1]-'a') + 1
			prefix[i] = (prefix[i]*base)%mod + t
			suffix[i] = (suffix[i]*base)%mod + s
		}
	}
	check := func(i, j, n, m int) bool {
		t := ((prefix[i]*mul[n])%mod + prefix[j]) % mod
		s := ((suffix[j]*mul[m])%mod + suffix[i]) % mod
		return t == s
	}
	var ans [][]int
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if check(i, j, len(words[j]), len(words[i])) {
				ans = append(ans, []int{i, j})
			}
			if check(j, i, len(words[i]), len(words[j])) {
				ans = append(ans, []int{j, i})
			}
		}
	}
	return ans
}

using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<int>> PalindromePairs(string[] words) {
        var results = new List<IList<int>>();
        var reverseDict = words.Select((w, i) => new {Word = w, Index = i}).ToDictionary(w => new string(w.Word.Reverse().ToArray()), w => w.Index);

        for (var i = 0; i < words.Length; ++i)
        {
            var word = words[i];
            for (var j = 0; j <= word.Length; ++j)
            {
                if (j > 0 && IsPalindrome(word, 0, j - 1))
                {
                    var suffix = word.Substring(j);
                    int pairIndex;
                    if (reverseDict.TryGetValue(suffix, out pairIndex) && i != pairIndex)
                    {
                        results.Add(new [] { pairIndex, i});
                    }
                }
                if (IsPalindrome(word, j, word.Length - 1))
                {
                    var prefix = word.Substring(0, j);
                    int pairIndex;
                    if (reverseDict.TryGetValue(prefix, out pairIndex) && i != pairIndex)
                    {
                        results.Add(new [] { i, pairIndex});
                    }
                }
            }
        }

        return results;
    }

    private bool IsPalindrome(string word, int startIndex, int endIndex)
    {
        var i = startIndex;
        var j = endIndex;
        while (i < j)
        {
            if (word[i] != word[j]) return false;
            ++i;
            --j;
        }
        return true;
    }
}

336 - Palindrome Pairs

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions