[알고리즘] 팰린드롬 페어

June·2021년 1월 28일
0

알고리즘

목록 보기
54/260

팰린드롬 페어

이 책에서 나온 문제 중 가장 어려운 문제 같다. 이해하려고 시간을 많이 투자했으나 아직도 완벽히는 이해하지 못했다.

책 풀이

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.val = char
        node.word_id = index

    def search(self, index, word) -> List[List[int]]:
        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

입력을 ['d', 'cbbcd', 'dcbb', 'dcbd', 'cbbc', 'bbcd']라고 가정하자. 이 입력 값을 뒤집어서 트라이를 만들면된다.

뒤집은 다음, 문자 단위로 내려가면서 트라이를 구현하고, 각각의 단어가 끝나는 지점에는 단어 인덱스를 word_id로 부여했다. 단어를 뒤집어서 구축한 트라이이기 때문에 입력값은 순서대로 탐색하다가, 끝나는 지점의 word_id 값이 -1이 아니라면, 현재 index와 해당 word_id는 팰린드롬으로 판별할 수 있다.
예를 들어 입력값 bbcd의 인덱스는 5이기 때문에, [5,2]인 bbcd + dcbb는 팰린드롬이다.

두 번째 판별 로직은 트라이 삽입 중에 남아 있는 단어가 팰린드롬이라면 미리 팰린드롬 여부를 세팅해 두는 방법이다. cbbc는 단어 자체가 팰린드롬이므로 루트에 바로 입력값의 인덱스인 p=4를 셋팅하고, word[0:len(word)-i]의 형태로 단어에서 문자 수를 계속 줄여 나가며 팰린드롬 여부를 체크한다. 문자가 하나만 남게 될 때는 항상 팰린드롬이므로 마찬가지로 p=4를 마지막에 셋팅한다. 당연히 이 마지막 값은 항상 w의 바로 앞 노드가 된다.

마지막인 세 번째 판별 로직은 입력값을 문자 단위로 확인해 나가다가 해당 노드의 word_id가 -1이 아닐 때, 나머지 문자가 팰린드롬이라면 팰린드롬으로 판별하는 경우다. dcbc + d가 이에 해당하는데 입력값 dcbc는 먼저 d부터 탐색하다가 d의 word_id가 -1이 아니기 때문에 나머지 문자 cbc에 대한 팰린드롬 여부를 검사한다. 여기서는 dcbc + d를 팰린드롬으로 판별한다.

0개의 댓글