[Leetcode] 208. Implement Trie (Prefix Tree)

haebin·2021년 4월 22일
0

목록 보기
54/60

문제 바로가기

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:
while word:
word = word[1:]

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

def startsWith(self, prefix: str) -> bool:
while prefix:
return False
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)