[파이썬 알고리즘 인터뷰][트라이] 팰린드롬 페어

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

리스트에 포함된 두 문자열이 더해져서 팰린드롬이 되는 문자열의 인덱스 pair들 출력

 

책에서 구현된 코드

import collections
from typing import List


# 트라이 저장할 노드
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:
            # 판별 로직 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

 

기억해야할 기법

• 어려운 문제일수록 자료구조를 만들어서 단순화하자

 

내가 구현한 코드

from typing import List

class TrieNode:
    def __init__(self, val: str = "", depth: int = -1, idx: int = -1):
        self.val = val
        self.idx = idx
        self.depth = depth
        self.child = dict()

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

    def insert(self, word: list[str], i: int) -> None:
        crnt = self.trie
        for d, c in enumerate(word):
            if c not in crnt.child:
                crnt.child[c] = TrieNode(c,d)
            crnt = crnt.child[c]
        crnt.idx = i

    def is_palindrome(self, word:str) -> bool:
        return word == word[::-1]

    def get_palindrome(self, words: str, searcher: int) -> List[int]:
        def dfs(crnt: TrieNode, apnd: str):
            result = []
            # 1. 단어 완성 2. 검색 대상과 다름 3. 펠린드롬 만족
            if crnt.idx != -1 and crnt.idx != searcher and self.is_palindrome(words+apnd):
                result.append(crnt.idx)

            for k, node in crnt.child.items():
                # 검색 대상과 펠린드롬이 불가능하다면 continue
                if node.depth < len(words) and node.val != words[node.depth]:
                    continue
                result += dfs(node, k+apnd)

            return result
        return dfs(self.trie, "")


class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        result = []

        for i, word in enumerate(words):
            trie.insert(list(word)[::-1], i)

        for i, word in enumerate(words):
            for j in trie.get_palindrome(word, i):
                if i != j:
                    result.append([i,j])

        return result

• 구현한 로직에 대한 예외상황이 중첩되었다
• 풀이를 떠올려도 구현이 안되는 너무 어려운 문제였다
• 속도 차이가 크다
  - 책에서 구현한 알고리즘의 속도가 2.3초 정도인데, 내가 구현한 알고리즘은 3.1초다
• 트라이 활용하는 문제를 더 풀어봐야겠다