문제 바로가기

Trie

In computer science, a trie, also called digital tree or prefix tree, is a type of search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters.

출처: wikipedia

node

class Node:
    def __init__(self):
        self.end = False
        self.children = dict()

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

    def insert(self, word: str) -> None:
        head = self.root
        while word:
            if word[0] not in head.children:
                head.children[word[0]] = Node()
            head = head.children[word[0]]
            word = word[1:]
        head.end = True

    def search(self, word: str) -> bool:
        head = self.root
        while word:
            if word[0] not in head.children:
                return False
            head = head.children[word[0]]
            word = word[1:]
        return head.end

    def startsWith(self, prefix: str) -> bool:
        head = self.root
        while prefix:
            if prefix[0] not in head.children:
                return False
            head = head.children[prefix[0]]
            prefix = prefix[1:]
        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

dictionary

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

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

    def search(self, word: str) -> bool:
        dic = self.trie
        for char in word:
            if char not in dic:
                return False
            dic = dic[char]
        return True if 'end' in dic else False
        
    def startsWith(self, prefix: str) -> bool:
        dic = self.trie
        for char in prefix:
            if char not in dic:
                return False
            dic = dic[char]
        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)