Problem statement

https://leetcode.com/problems/palindrome-pairs/

Solution

Let n be number of words and k be average length of word. Then there is trivial algorithm with complexity O(n^2k). There is better algorithm: for each word we can evaluate all prefixes and suffixes, and check if they are palindromes: for example if we have abcxxyxx, cba, if we want to combine them we need suffix xxyxx to be palindrome; if we want to combine abc, xyyxcba, we want prefix xyyx to be palindrome. So we do the following steps:

  1. For each word, and each suffix/prefix of length i, we check if it is palindrome and if it is, we put prefix/suffix to our hash table W_d. Note, that for the case abcxxyxx we found suffix xxyxx which is palindrome, but we put prefix abc to our hash table. Note also that we need to handle the cases of empty suffixes/prefixes. For example if we have abc and cba, then we can connect these two strings in two ways, and we can say that we take empty prefix/suffix here. So, what will be kept in W_d is pairs (t, ind), where ind is index of word and first element is -1 for non-empty prefix, 1 for non-empty suffix and 0 for empty suffix or prefix.
  2. Now, we want to iterate through our W once again and for any word we look at W_d[word[::-1]]: possible candidates for this word. We need to make sure that candidate we found is not equal to word we consider at the moment. Next, if one < 0, it means, that we consider non-empty prefixes, that is why we consider one <= 0 and append pair to our final answer. Same logic is for one >= 0. In this way for non-empty prefixes/suffixes we will deal with them only once and for empty we deal with them twice as it should be.
  3. In the end we remove duplicates: return set.

Complexity

For each word we make O(k^2) preprocessing, so in total we have O(nk^2) time for the first step. For the second step we traverse each element in values of W_d only once and we have no more than O(n^2) of them, so total time complexity is O(nk^2 + n^2). Space complexity is O(n^2).

Code

class Solution:
    def palindromePairs(self, W):
        W_d, ans = defaultdict(list), []

        for idx, word in enumerate(W):
            W_d[word].append([0, idx])
            for i in range(1, len(word) + 1):
                suff, pref = word[:i], word[i:]
                if suff == suff[::-1]:
                    W_d[pref].append([- (pref != ""),idx])
                if pref == pref[::-1]:
                    W_d[suff].append([+ (suff != ""),idx])
                    
        for idx, word in enumerate(W):
            for one, two in W_d[word[::-1]]:
                if idx != two and one <= 0: 
                    ans.append((idx, two))
                if idx != two and one >= 0: 
                    ans.append((two, idx))
                    
        return set(ans)