[DSA][Trie] 02. Design Add and Search Words Data Structure

LeetCode 211

 

02. Design Add and Search Words Data Structure

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:
- WordDictionary() Initializes the object.
- void addWord(word) Adds word to the data structure, it can be matched later.
- bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

 

 

[질문하기]

- addWord에 전달되는 word에 .이 포함될 수 있나요? NO

- word는 대소문자를 구분하나요? NO

 

[아이디어]

- Trie 자료구조를 사용하되, search 시에 .이 나오면 현재 노드의 모든 자식 노드를 재귀적으로 탐색한다.

 

 

[풀이 1] Trie

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

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

    def addWord(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:
        def dfs(j, root):
            cur = root
            for i in range(j, len(word)):
                c = word[i]
                if c == ".":
                    for child in cur.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if c not in cur.children:
                        return False
                    cur = cur.children[c]
            return cur.isLastChar
        return dfs(0, self.root)

TrieNode의 구조와 addWord는 전형적인 Trie 자료구조와 같다. 하지만 "." 문자가 등장하는 경우, search 함수의 동작 방식이 달라진다. "."은 모든 알파벳과 매칭되므로, 이 문자를 만났을 때는 cur.children에 있는 모든 자식 노드들에 대해 탐색을 해야 한다. 이때 하나의 브랜치라도 매칭되는 브랜치가 나오면 True를 반환해야 한다.

이를 위해 깊이 우선 탐색(DFS) 방식의 재귀 함수를 작성하여 "." 다음에 오는 단어를 인자로 넘기면서, 각 자식 노드에서 다시 매칭 여부를 확인할 수 있도록, 인덱스와 현재 노드를 재귀적으로 넘겨주며 탐색한다.

 

 

⏱️ 시간복잡도

search에 들어오는 단어에는 최대 2개의 "."만 포함될 수 있으므로, 분기(branching)는 최대 26² = 676가지로 이루어지지만, 이는 상수 시간 내에 처리 가능한 수준이므로 전체 시간 복잡도는 단어 길이를 n이라 할 때 O(n) 으로 볼 수 있다.

🧠 공간복잡도

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