---
title: "211. Design Add and Search Words Data Structure"
url: "https://laigary.com/interview/coding/211-design-add-and-search-words-data-structure"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-08-02"
tags: ["Trie"]
---

# 211. Design Add and Search Words Data Structure

[211\. Design Add and Search Words Data Structure](https://leetcode.com/problems/design-add-and-search-words-data-structure/)

設計一個資料結構，支援 `addWord` 加入單字、`search` 查詢單字，而查詢字串裡的 `.` 可以匹配**任何一個**字元。

## 思路

這一題比較特別，需要模糊比對搜尋的字串，主要也要用到 Trie，除了紀錄字元以外，可以用特殊的字元記錄額外資訊。

### Trie 用巢狀 dict 就夠

不用另外開節點類別，一層 dict 就是一個節點，key 是字元、value 是下一層：

```text
addWord("bad") ->  {'b': {'a': {'d': {'$': True}}}}
```

`'$'` 就是那個「特殊的字元」—— 它不是任何字元的分支，而是標記**這裡可以結束**。沒有它就分不出「`bad` 有被加進去」和「`bad` 只是 `badly` 的前綴」。也因為 `'$'` 混在同一層 dict 裡，走訪分支時要記得把它跳過。

### `.` 是唯一需要遞迴的地方

沒有 `.` 的話，`search` 就是一路 `node = node[char]` 走下去，完全不用遞迴。

碰到 `.` 才會分岔：**這一層的每個分支都要試一次**，任何一條成功就成功。所以遞迴的意義是「從下一個字元開始，在這個分支底下繼續找」。

嘗試完所有分支都失敗之後，程式會往下走到 `if char not in node`。因為 `.` 不會是 trie 裡的 key，這裡必定回傳 `False` —— 剛好就是「所有分支都試過了，沒有一條成立」。

## 解題方向

```python
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = {}

    def addWord(self, word: str) -> None:
        node = self.trie
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node['$'] = True


    def search(self, word: str) -> bool:
        def search_in_node(start, node) -> bool:
            for i in range(start, len(word)):
                char = word[i]
                if char == '.':
                    for x in node:
                        if x != '$' and search_in_node(i + 1, node[x]):
                            return True
                if char not in node:
                    return False
                else:
                    node = node[char]
            return '$' in node
        return search_in_node(0, self.trie)


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

```

遞迴傳的是**索引**而不是 `word[i+1:]`。這一點值得留意：`.` 會讓每一層分岔成最多 26 條，如果每條都切一份剩餘字串，光是複製就會乘上分支數。改成傳 `i + 1`、迴圈用 `range(start, len(word))`，其他邏輯一行都不用動。

## 複雜度

設 $L$ 是單字長度、$N$ 是已加入的單字數、$\Sigma$ 是字元集大小（小寫英文是 26）。

**addWord**
- 時間 $O(L)$ — 一個字元走一層
- 空間 $O(L)$ — 最壞情況每個字元都要開一層新的 dict

**search**
- 時間 沒有 `.` 時 $O(L)$；全部都是 `.` 時最壞 $O(\Sigma^L)$ — 每一層都要展開所有分支。實際上會被 trie 裡真正存在的分支數擋住，所以上界也可以寫成 $O(N \times L)$
- 空間 $O(L)$ — 遞迴深度最多就是字串長度

**整體空間** $O(N \times L)$ — 所有單字的字元總數，共用前綴的部分會合併掉。