[파이썬 알고리즘 인터뷰][트라이] 트라이 구현

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

---

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

 

문제 정의

트라이 구현하기

 

책에서 구현된 코드

import collections


# 트라이의 노드
class TrieNode:
    def __init__(self):
        self.word = False
        self.children = collections.defaultdict(TrieNode)


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

    # 단어 삽입
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children[char]
        node.word = True

    # 단어 존재 여부 판별
    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]

        return node.word

    # 문자열로 시작 단어 존재 여부 판별
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]

        return True

 

기억해야할 기법

• Class로 선언한 객체 사용
  
  • 트라이에 문자 확인 외에 기능이 필요할 경우, 책에서 구현한 방법과 같이 TrieNode를 선언하여 이용

 

내가 구현한 코드

class Trie:
    word = "word"

    def __init__(self):
        self.trie = dict()

    def insert(self, word: str) -> None:
        trie = self.trie
        for c in word:
            if c not in trie:
                trie[c] = dict()
            trie = trie[c]
        trie[self.word] = True

    def search(self, word: str) -> bool:
        trie = self.trie
        for c in word:
            if c not in trie:
                return False
            trie = trie[c]
        return self.word in trie

    def startsWith(self, prefix: str) -> bool:
        trie = self.trie
        for c in prefix:
            if c not in trie:
                return False
            trie = trie[c]
        return True

• 나는 trie 딕셔너리에 담길 key가 char(길이 1인 string)임을 이용
• word의 경우 길이 2 이상의 string key "word"를 담아 search에서 "word" key를 확인
• Class 생성이 없어서 그런지 속도와 메모리 면에서 책에서 구현한 알고리즘보다 좋음
• 그러나 현업에서 이런 방식으로 개발하면 큰일날듯...