LeetCode 208. Implement Trie (Prefix Tree) (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.

 

 

 

풀이

 

 

TrieTree를 구현하는 직접 구현해서 만드는 문제이다.

보통 for문과 재귀를 사용해서 검색하고 찾는방법을 만드는데 , 저번에 재귀를 많이 사용해봤으니 이번에는 for문을 통해 만들어봐야겠다.

 

트라이트리는 검색을 구현할 때 많이 사용하는데, 해시맵(딕셔너리)를 사용해서 만들면 비교적 빠르게 트리를 탐색하여 값을 반환 할 수 있다. 

 

1.노드에 다음 탐색경로를 알려 줄 수 있는 children를 딕셔너리로 지정, endof를 통해서 문자가 완성된 문자인지 확인, 

2.탐색시 각 문자열의 딕셔너리에 들어있는 문제의 인덱스를 확인한다  ex) dict[char] 

3. 존재한다면 현재 노드에서 딕셔너리 안의 노드로 이동, 존재하지 않는다면 딕셔너리에 node생성 후 이동

4. 문자 탐색이 끝났을 때 endof 가 True라면 존재하는 문자

 

class Node:
    def __init__(self):
        self.children={}
        self.endof =False

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

    def insert(self, word): # 노드 삽입, 딕셔너리로 존재하지않는다면 생성, 존재한다면 추가 
        node = self.root
        for i in word:
            if i not in node.children:
                node.children[i] = Node() # 딕셔너리에 존재하지않는다면, node 추가,
            node= node.children[i] 
        node.endof =1   # 마지막 문자에 완성을 알려줄 수 있도록 endof = Ture 설정 
            
    def search(self, word):
        cur = self.root
        for i in word: 
            if i not in cur.children:
                return False  # 트라이트리하위에 글자가 존재하지 않는다면 False 반환
            cur = cur.children[i 
        if cur.endof ==1: # 마지막 탐색에서 endof가 Ture인지 확인, 
            return True
         retrun False


    def startsWith(self, prefix): #접두사 확인, 
        cur = self.root 
        for i in prefix:
            if i not in cur.children: # 트라이트리하위에 글자가 존재하지 않는다면 False 반환
                return False
            cur = cur.children[i] # 존재한다면 자식의 노드로 이동
 


# 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)

 

 

 

다른사람의 코드

 

 

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False
        
class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        def fun(index, root):
            if index == len(word):
                root.end = True
                return
            
            if word[index] not in root.children:
                root.children[word[index]] = TrieNode()
                
            fun(index+1, root.children[word[index]])
                
        fun(0, self.root)
        
    def search(self, word: str) -> bool:
        def fun(index, root):
            if index == len(word):
                if root.end:
                    return True
                else:
                    return False
            
            if word[index] in root.children:
                return fun(index+1, root.children[word[index]])
            
            return False
        
        return fun(0, self.root)
        

    def startsWith(self, prefix: str) -> bool:
        def fun(index, root):
            if index == len(prefix):
                return True
            
            if prefix[index] in root.children:
                return fun(index+1, root.children[prefix[index]])
            
            return False
        
        return fun(0, self.root)

 

기본적으로 딕셔너리를 생성해서 하위 문자열을 찾고, for문을 사용해서 찾는게 아니라 재귀를 통해서 하위노드로 찾아내려간다,