336. Palindrome Pairs

 

문제

 

단어 리스트에서 words [i] + words [j]가 팰린드롬이 되는 모든 인덱스 조합 (i, j)를 구하라

 

ex)

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

 

 

해설

 

처음 봤을 땐 브루트포스로 쉽게 해결 가능해 보였지만 역시나 hard 문제답게 TLE가 떠버림..

 

결국 Trie를 써서 해결해야 되는 문젠데..

 

Trie 자체는 이해가 되는데 팰린드롬이 되는 경우의 수를 따지는 게 어려웠다.

 

결국 답도 보고 검색도 해보고 이해는 된 상황!

 

그냥 가져와봤다

 

 

우선 코드부터 보자!

 

 

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):
        result = []
        node = self.root
 
        while word:
            # 판별 로직 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:]
 
        # 판별 로직 1
        if node.word_id >= 0 and node.word_id != index:
            result.append([index, node.word_id])
 
        # 판별 로직 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

Trie가 뭔지는 알거라 생각하고 설명은 생략하겠음.

 

판별 로직 1,2,3이 있는데 우선

 

1. abc + cba같은 케이스

 

2. abc + ba같은 케이스

 

3. cb + abc같은 케이스

 

로 나눌 수 있다.

 

한 번 팰린드롬이 어떤 케이스로 나눠질 수 있는지 직접 생각해보면 빠르다.

 

 

지저분하긴 한데 이런 식으로 그려보자