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