[Leetcode 208] - Implement Trie (Prefix Tree) w/ Python

 

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 # 접두사 끝까지 도달했을때 있었다