← 전체 회차
a-062-design-add-and-search-words-data-structure2026-07-14mediumleetcode #211neetcode150

단어 추가 및 검색 데이터 구조 설계

#string#depth-first-search#design#trie
↗ leetcode #211 · a-062-design-add-and-search-words-data-structure
01

문제

· problem
P.a-062-design-add-and-search-words-data-structure

단어 추가 및 검색 데이터 구조 설계

↗ leetcode #211

새로운 단어를 추가하고 이전에 추가된 문자열과 일치하는지 확인하는 기능을 지원하는 데이터 구조를 설계하세요. WordDictionary 클래스를 구현하세요: - WordDictionary(): 객체를 초기화합니다. - void addWord(word): 데이터 구조에 word를 추가하며, 나중에 검색할 수 있습니다. - bool search(word): 데이터 구조에 word와 일치하는 문자열이 있으면 true를, 없으면 false를 반환합니다. word는 도트('.')를 포함할 수 있으며, 도트는 어떤 문자와도 일치할 수 있습니다.

제약
  • · 1 ≤ word.length ≤ 25
  • · word in addWord consists of lowercase English letters
  • · word in search consists of '.' or lowercase English letters
  • · At most 2 dots in search queries
  • · At most 10^4 total calls to addWord and search
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
[null, null, null, null, false, true, true, true]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    search 메서드에서 도트('.')는 정확히 하나의 문자와 일치하나요, 아니면 0개 이상?
  • ☐
    같은 단어를 여러 번 추가할 수 있나요?
  • ☐
    이 문제를 해결하기 위해 트라이(Trie) 자료구조를 사용해야 하나요?
  • ☐
    search 메서드에서 도트를 만나면 모든 자식 노드를 확인해야 하나요?
  • ☐
    HashSet만 사용하여 이 문제를 해결할 수 있나요?
  • ☐
    정규식(regex)을 사용하면 이 문제를 더 간단하게 해결할 수 있나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 트라이 루트 초기화
○
self.root = TrieNode()
○
self.root = {}
○
self.root = None
step 2· addWord에서 트라이 순회/구축│ 중첩
○
cur = self.root
○
cur = self.root
for c in word:
    cur.children[c] = TrieNode()
○
while len(word) > 0:
    c = word.pop(0)
    cur.children[c] = TrieNode()
step 3· 단어 끝 표시│ 중첩
○
cur.word = True
○
self.root.word = True
○
cur.children = True
step 4· DFS 재귀 함수 정의
○
def dfs(j, root):
○
def search(self, word: str) -> bool:
    cur = self.root
    for c in word:
        if c != '.' and c not in cur.children:
            return False
        if c != '.':
            cur = cur.children[c]
○
for i, c in enumerate(word):
    if c in cur.children:
        cur = cur.children[c]
step 5· 도트 와일드카드 처리│ │ 중첩
○
if c == ".":
○
if c == '.':
    if len(cur.children) > 0:
        return True
○
if c == '.':
    for child in cur.children.values():
        return dfs(i + 1, child)
step 6· 일반 문자 처리│ │ 중첩
○
else:
○
if c in cur.children:
    cur = cur.children[c]
else:
    return True
○
cur = cur.children.get(c, cur)
step 7· 단어 일치 여부 반환│ 중첩
○
return cur.word
○
return True
○
return len(cur.children) > 0
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class TrieNode:
2
    def __init__(self):
3
        self.children = {}  # a : TrieNode
4
        self.word = False
5
6
7
class WordDictionary:
8
    def __init__(self):
9
        self.root = TrieNode()
10
11
    def addWord(self, word: str) -> None:
12
        cur = self.root
13
        for c in word:
14
            if c not in cur.children:
15
                cur.children[c] = TrieNode()
16
            cur = cur.children[c]
17
        cur.word = True
18
19
    def search(self, word: str) -> bool:
20
        def dfs(j, root):
21
            cur = root
22
23
            for i in range(j, len(word)):
24
                c = word[i]
25
                if c == ".":
26
                    for child in cur.children.values():
27
                        if dfs(i + 1, child):
28
                            return True
29
                    return False
30
                else:
31
                    if c not in cur.children:
32
                        return False
33
                    cur = cur.children[c]
34
            return cur.word
35
36
        return dfs(0, self.root)
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
→
[null, null, null, null, false, true, true, true]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.