336. Palindrome Pairs

Hard

Problem:

Find all index combinations (i, j) from the word list where words[i] + words[j] forms a palindrome.

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

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

What to learn:

@staticmethod Decorator

staticmethod is similar to Java's static declaration. When a method is defined this way, it strongly takes on the meaning of a function, independent of the class. Indeed, the always-present self parameter in class methods is omitted, and the function itself is declared with a separate data type.

class CLASS:
    def a(self):
        pass
    @staticmethod
    def b():
        pass

When called directly from outside without creating an instance of the class, the type for both becomes a function.

>>> type(CLASS.a), type(CLASS.b)
(<class 'function'>, <class 'function'>)

However, after creating an instance of the class and checking the type of the function, the function within the class now becomes a method. But a function declared with @staticmethod is still recognized as a function. This means it retains the meaning of an independent function, rather than a method of the class. Essentially, it holds the same meaning as if the function was declared separately outside of the class.

cls = CLASS()
>>> type(cls.a), type(cls.b)
(<class 'method'>, <class 'function'>)

Doing this restricts access to the class instance just like with class methods. Therefore, it's often used when you want to clearly declare a function as independent and limit access to the class instance.

Solution:

To solve this in $O(n)$, you need to traverse each input value once. Since you need to determine if it's a palindrome, you can construct a trie by reversing the input values.

1. After reversing the input values, implement the trie by continuously descending at each character level. At the point where each word ends, assign the word index as the word_id. Therefore, if there is a word_id at the end of the search, it is determined to be a palindrome.

2. During the trie insertion, if the remaining word forms a palindrome, the corresponding index is pre-stored in palindrome_word_ids. The word_id indicates the end of a word, and palindrome_word_ids is always set on the node before the word_id. This is because when only one character remains, it is always a palindrome. Therefore, if there is a palindrome_word_ids at the end of the search, it is determined to be a palindrome.

3. As you check the input value character by character, if the word_id of the current node is not -1, meaning there is a word_id in the middle of the search, and the remaining characters form a palindrome, then it is determined to be a palindrome.

When the maximum length of a word is set to $k$, it becomes $O(k^2n)$. In the case of a brute-force solution, it becomes $O(kn^2)$. In this problem, since $k$ is much smaller, the trie solution is more efficient.

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.word_id = -1
        self.palindrome_word_ids = []

class Trie:
    def __init__(self):
        self.root = TrieNode()

    @staticmethod
    def is_palindrome(word: str) -> bool:
        return word == word[::-1]

    def insert(self, index, word) -> None:
        node = self.root
        for i, char in enumerate(reversed(word)):
            if self.is_palindrome(word[0:len(word) - i]):
                node.palindrome_word_ids.append(index)
            node = node.children[char]

        node.word_id = index

    def search(self, index, word) -> List[List[int]]:
        result = []
        node = self.root

        while word:
            # Logic 3
            if node.word_id >= 0:
                if self.is_palindrome(word):
                    result.append([index, node.word_id])
            if not word[0] in node.children:
                return result
            node = node.children[word[0]]
            word = word[1:]

        # Logic 1
        if node.word_id >= 0 and node.word_id != index:
            result.append([index, node.word_id])
        # Logic 2
        for palindrome_word_id in node.palindrome_word_ids:
            result.append([index, palindrome_word_id])

        return result

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        for i, word in enumerate(words):
            trie.insert(i, word)

        results = []
        for i, word in enumerate(words):
            results.extend(trie.search(i, word))

        return results

Brute Force: Time Limit Exceeded

Time Complexity: $O(kn^2)$

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

        output = []

        for i, word1 in enumerate(words):
            for j, word2 in enumerate(words):
                if i == j:
                    continue
                if is_palindrome(word1 + word2):
                    output.append([i, j])

        return output