← 전체 회차
a-061-implement-trie-prefix-tree2026-07-13mediumleetcode #208neetcode150

트라이(접두사 트리) 구현

#hash-table#string#design#trie
↗ leetcode #208 · a-061-implement-trie-prefix-tree
01

문제

· problem
P.a-061-implement-trie-prefix-tree

트라이(접두사 트리) 구현

↗ leetcode #208

트라이(트라이라고 발음하며 "prefix tree"라고도 불림)는 문자열 데이터셋에서 키를 효율적으로 저장하고 검색하기 위한 트리 데이터 구조입니다. 자동 완성(autocomplete)과 철자 검사(spellchecker) 등 다양한 애플리케이션에서 활용됩니다. Trie 클래스를 구현하세요: - Trie(): 트라이 객체를 초기화합니다. - void insert(String word): 문자열 word를 트라이에 삽입합니다. - boolean search(String word): 문자열 word가 트라이에 있으면 true를 반환하고, 없으면 false를 반환합니다. (즉, 이전에 삽입된 word여야 합니다) - boolean startsWith(String prefix): 이전에 삽입된 문자열 중에서 prefix로 시작하는 문자열이 있으면 true를 반환하고, 없으면 false를 반환합니다.

제약
  • · 1 ≤ word.length, prefix.length ≤ 2000
  • · word and prefix consist only of lowercase English letters
  • · At most 3 * 10^4 calls in total will be made to insert, search, and startsWith
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
[null, null, true, false, true, null, true]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    search() 메서드와 startsWith() 메서드의 차이는 무엇인가요?
  • ☐
    노드에서 어떻게 단어의 끝을 표시해야 하나요?
  • ☐
    한 단어가 다른 단어의 접두사가 될 수 있나요?
  • ☐
    자식 노드를 저장할 때 배열과 해시맵 중 어느 것이 더 좋나요?
  • ☐
    문자를 배열 인덱스로 변환할 때 ord(c) - ord('a')를 사용하는 이유는 무엇인가요?
  • ☐
    경로가 존재하지 않으면 즉시 false를 반환해야 하나요?
  • ☐
    이미 존재하는 단어를 다시 insert()하면 어떻게 되나요?
  • ☐
    startsWith()에서 경로가 존재하면 항상 true를 반환해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 루트 노드 초기화
○
self.root = TrieNode()
○
self.root = {}
○
self.children = [None] * 26
step 2· 문자를 배열 인덱스로 변환│ │ 중첩
○
i = ord(c) - ord("a")
○
i = ord(c)
○
i = ord(c) - ord('A')
step 3· insert에서 자식 노드 생성│ │ 중첩
○
curr.children[i] = TrieNode()
○
curr.children[i] = {}
○
if curr.children[i] is not None: curr.children[i] = TrieNode()
step 4· insert에서 단어의 끝 표시│ 중첩
○
curr.end = True
○
self.root.end = True
○
curr.children[i].end = True
step 5· search에서 단어 완성 확인│ 중첩
○
return curr.end
○
return curr is not None
○
return True
step 6· startsWith에서 문자 순회│ 중첩
○
for c in prefix:
○
for c in word:
○
for i in range(len(prefix)): c = prefix[i]
step 7· startsWith에서 경로 존재 확인│ 중첩
○
return True
○
return curr.end
○
return curr is not None
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class TrieNode:
2
    def __init__(self):
3
        self.children = [None] * 26
4
        self.end = False
5
6
7
class Trie:
8
    def __init__(self):
9
        """
10
        Initialize your data structure here.
11
        """
12
        self.root = TrieNode()
13
14
    def insert(self, word: str) -> None:
15
        """
16
        Inserts a word into the trie.
17
        """
18
        curr = self.root
19
        for c in word:
20
            i = ord(c) - ord("a")
21
            if curr.children[i] is None:
22
                curr.children[i] = TrieNode()
23
            curr = curr.children[i]
24
        curr.end = True
25
26
    def search(self, word: str) -> bool:
27
        """
28
        Returns if the word is in the trie.
29
        """
30
        curr = self.root
31
        for c in word:
32
            i = ord(c) - ord("a")
33
            if curr.children[i] is None:
34
                return False
35
            curr = curr.children[i]
36
        return curr.end
37
38
    def startsWith(self, prefix: str) -> bool:
39
        """
40
        Returns if there is any word in the trie that starts with the given prefix.
41
        """
42
        curr = self.root
43
        for c in prefix:
44
            i = ord(c) - ord("a")
45
            if curr.children[i] is None:
46
                return False
47
            curr = curr.children[i]
48
        return True
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
→
[null, null, true, false, true, null, true]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.