A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
● Trie() Initializes the trie object.
● void insert(String word) Inserts the string word into the trie.
● boolean search(String word) True if the string word is in the trie and False otherwise.
● boolean startsWith(String prefix) True if there is a string word that has the prefix and False otherwise.
접두사 트리는 단어를 데이터셋에 효율적으로 저장 및 불러오기를 하는 자료구조다
이를 통해 문법 확인 및 자동완성 기능을 사용할때 유용하다
Trie 클래스를 만들어야 된다:
● Trie()는 Object를 만든다
● void insert(String word)는 Trie에 word 이라는 String을 저장한다
● boolean search(String word)는 트리에 해당 단어가 있는지 확인한다 True/False 리턴
● boolean startsWith(String prefix) 는 트리에 해당 접두사가 있는지 확인한다 True/False 리턴
https://leetcode.com/problems/implement-trie-prefix-tree/description/
Example 1:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
트리에 해당 단어가 있는지 또는 접두사가 있는지 확인하기 위해서는 각 글자를 확인해야된다
이를 통해 Node가 될 TrieNode를 먼저 만들어 각 단어를 효율적으로 저장할 Dictionary와
단어의 끝인지 확인하는 wordEnd를 만들어서 단어를 확인하는 방법을 만들었다
이를 통해 각 글자마다 트리 노드를 저장해 자식 노드로 내려가는 형식을 만들어서 단어가 있다면 접두사도 확인할 수 있다
class TrieNode:
def __init__(self):
self.letters = {}
self.wordEnd = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
curr = self.root
for char in word: # 각 단어의 글자마다
if char not in curr.letters: # 이미 해당 글자 자리에 없는 글자라면
curr.letters[char] = TrieNode() # 새로운 노드를 만들어서 추가한뒤
curr = curr.letters[char] # 다음 글자로 넘어간다
curr.wordEnd = True # 만약 단어의 끝이라면 표시를 남긴다
def search(self, word: str) -> bool:
curr = self.root
for char in word: # 각 단어의 글자마다
if char in curr.letters: # 해당 글자가 있다면 다음 글자로 넘어간다
curr = curr.letters[char]
else:
return False # 아니라면 해당 글자가/단어가 없다
return curr.wordEnd # 끝에 도달했을때 그 단어가 일치하면 True
def startsWith(self, prefix: str) -> bool:
curr = self.root
for char in prefix: # 똑같이 글자마다
if char in curr.letters:
curr = curr.letters[char] # 있는지 확인한다
else:
return False
return True # 접두사 끝까지 도달했을때 있었다

'알고리즘 & 자료구조 > Leetcode' 카테고리의 다른 글
[Leetcode 212] - Word Search II w/ Python (0) | 2024.04.11 |
---|---|
[Leetcode 211] - Design Add and Search Words Data Structure w/ Python (0) | 2024.04.11 |
[Leetcode 297] - Serialize and Deserialize Binary Tree w/ Python (1) | 2024.04.11 |
[Leetcode 124] - Binary Tree Maximum Path Sum w/ Python (0) | 2024.04.11 |
[Leetcode 105] - Construct Binary Tree from Preorder and Inorder Traversal w/ Python (0) | 2024.04.11 |