LC 0336 [H] Palindrome Pairs - ALawliet/algorithms GitHub Wiki

Time complexity of this solution is O(n * w^2) n being length of the list, w being the average word length. It is not better or worse than O(n^2), if the average word length is very long this solution is very slow, but with very long list and every word is very short this is a much better solution.

if back == word then the word itself is a palindrome.
We want to skip this case because we know the list of words are unique, otherwise we would double count the number palindrome pairs

Better explained with an example :

Consider the word "abandon" - with prefix aba - now if you could find the reverse of the suffix(ndon) = "nodn" in rest of your word list, it'd do the trick:

nodn + aba + ndon = nodnabandon - which happens to be a palindrome.

But lets say you had the word "london" - no matter if you have "nodn",

nodn + lo + ndon ---> Not happening ! :D

First if checks for isPalindrome(suffix reversed + prefix + suffix);

Second if checks for isPalindrome(prefix + suffix + prefix reversed).

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        def is_palindrome(string):
            return string == string[::-1]

        # map with index
        words = {word: i for i, word in enumerate(words)}

        palins = []
        for word, idx in words.items():
            for i in range(len(word) + 1):
                prefix = word[:i]
                suffix = word[i:]

                if is_palindrome(prefix):
                    rev = suffix[::-1]
                    if rev != word and rev in words:
                        palins.append([words[rev], idx])

                if i != len(word) and is_palindrome(suffix):
                    rev = prefix[::-1]
                    if rev != word and rev in words:
                        palins.append([idx, words[rev]])

        return palins