python으로 Trie 구현 with defaultdict

class TrieNode:
    def __init__(self):
        self.word = False
        self.children = dict()

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

    def insert(self,word : str) -> None:
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            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

trie = Trie()

trie.insert('apple')

if trie.search('appe'):
    print("YES")
else:
    print("NO")


### childeren 부분을 dict가 아닌 defaultdict를 이용

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


trie = Trie()

trie.insert('apple')

if trie.search('apple'):
    print("YES")
else:
    print("NO")

 

그냥 dict를 사용하는것과 defaultdict를 사용하는 것에 대한 차이는

 

insert부분에서 childeren이 없을때 에서 차이가 난다

 

먼저 dict 해당 알파벳에 대한 자식이 있는지 if 문을 통하여 확인하여 없다면 Trienode를 할당 해줘야되지만

 

defaultdict는 해당 자신이 없다면 자동으로 생성해주기 때문에 if문을 굳이 사용하지 않아도 된다.