[DSA][Trie] 01. Implement Trie (Prefix Tree)

LeetCode 208

 

01. Implement Trie (Prefix Tree)

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.

 

 

[풀이 1] Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isLastChar = False

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

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.isLastChar = True

    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.isLastChar

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

Trie (트라이)는 문자열을 효율적으로 저장하고 탐색하기 위한 트리 기반 자료구조이다. 문자열의 각 char를 한 노드로 나타내며, 공통 접두사를 기준으로 분기시켜 저장한다.

단어 "apple", "app", "dog", "dot", "die" 다섯 개를 Trie에 삽입한다고 하면, 루트 노드를 기준으로 위와 같이 분기되는 트리 구조를 갖게 된다. 이때 공통 접두사를 공유하는 단어들은 하나의 경로를 따라 연결되고, 이후 문자에서 분기된다.

각 노드는 해당 문자를 기준으로 다음 문자를 연결하는 자식 노드들을 HashMap으로 저장한다. HashMap에서 key는 문자(char), value는 다음 노드를 가리킨다.

또한, 어떤 노드가 단어의 마지막 문자인지를 구분하기 위해 isLastChar와 같은 boolean 플래그를 사용한다. 이 플래그가 true인 경우, 해당 노드까지의 경로가 유효한 단어임을 의미하기 때문에 search 메서드에서 단어를 모두 탐색한 후 이 flag를 체크함으로써 "apple"이라는 단어만 있을 때 "app"을 찾은 경우와 "app"이 실제로 존재하는 경우를 구분할 수 있다.

 

 

⏱️ 시간복잡도

각 함수는 입력으로 주어진 단어를 문자 단위로 순회하므로, 단어의 길이를 n이라고 할 때 시간 복잡도는 O(n)이다.

🧠 공간복잡도

Trie는 문자마다 새로운 노드를 생성하므로, 전체 TrieNode의 수를 t라고 하면 공간 복잡도는 O(t)이다.