[LEET CODE] 208. Implement Trie (Prefix Tree)

# Problem

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) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.   Constraints: 1 <= word.length, prefix.length <= 2000 word and prefix consist only of lowercase English letters. At most 3 * 104 calls in total will be made to insert, search, and startsWith.

insert(word) : word 삽입  

search(word) : word가 존재하면 true 리턴 

strartsWith(prefix) : prefix 로 시작하는 단어가 있으면 true 리턴 

 

# Solution

import collections


# 트라이의 노드
class TrieNode:
    def __init__(self):
        self.word = False
        self.children = collections.defaultdict(TrieNode)


class Trie:
    def __init__(self):
        self.root = TrieNode()

    # 단어 삽입
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children[char]
        node.word = True

    # 단어 존재 여부 판별
    def search(self, word: str) -> bool:
        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: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]

        return True

1. insert : children은 defaultdict(TrieNode)로 디폴트 자동 생성 -> word의 한문자마다 node.children에 넣어줌

                모두 넣으면 node.word = True를 통해 단어의 끝 노드 표시

2. search : word의 모든 문자에 대해서 node.children을 확인하면서 없는 단어가 있는 경우 False 리턴

                   끝까지 있으면 for문 빠져나오고 node.word 값 리턴

3. startsWith : prefix의 문자들에 대해서 존재하지 않으면 False 리턴

                          prefix의 모든 문자 존재하면 for문 끝나고 True 리턴

---

# 트라이 ( Trie )

검색트리의 일종으로 일반적으로 키가 문자열인 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조

자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 쓰임

문자 개수만큼 자식이 있음 ( 한 문자씩 연결 )

트라이에서는 각 문자열의 길이만큰만 탐색하면 원하는 결과를 찾을 수 있음