[leetcode 208] Implement Trie

심지훈·2021년 6월 16일
0

leetcode

목록 보기
17/21

문제 링크

이 문제는 트라이 자료구조를 구현하는 문제이다.
트라이는 트리 구조를 이용해서 문자열을 쉽게 탐색할 수 있도록 하는 자료구조이다.
한 노드에 한 문자씩 넣어서 트리를 만든다.
파이썬에서는 딕셔너리로 간단하게 구현을 했다.

import collections

class TrieNode:
    def __init__(self) -> None:
        self.word = False
        self.children = collections.defaultdict(TrieNode)

class Trie:

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

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.children[char]

        node.word = True

    def search(self,word):
        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):
        node = self.root
        for char in word:
            if char not in node.children:
                return False

            node = node.children[char]

        return True
profile
유연한 개발자

0개의 댓글