陳憲億 Joseph Chen | Software Engineer & AI Developer

Joseph Chen

2026

13 min read

3 題精講

你有沒有想過，Google 搜尋框的自動補全是怎麼做的？輸入「app」，立刻出現「apple」「application」「approach」…… 背後的資料結構就是 Trie（前綴樹 / 字典樹）。

Trie 是一種專門為字串前綴搜尋設計的樹狀結構。它能在 O(L)（L 為字串長度）的時間內完成插入和搜尋，不管你存了幾百萬個單字。

這篇從零實作 Trie，再接兩道進階題打通。

Trie 長什麼樣子？

假設要儲存 ["app", "apple", "apt", "bat"]：

Trie 結構示意（綠點 ✓ = 是某個單字的結尾）

root

p✓

e✓

t✓

「app」和「apple」共享 root→a→p→p 的前綴節點。Trie 的核心就是共享前綴。

🌳

每個節點

代表一個字元。根節點不代表任何字元，只是起點。

✅

is_end 旗標

標記「到這個節點為止，是一個完整的單字」。沒有 is_end 就只是前綴。

📦

children 字典

每個節點最多有 26 個子節點（小寫英文字母）。通常用 dict 或長度 26 的陣列實作。

🏗️

Part 1 — Implement Trie

#208 · Medium · 從零實作前綴樹

題目

實作一個 Trie 類別，支援三個操作：

insert(word)：插入一個單字
search(word)：搜尋整個單字是否存在，回傳 True/False
startsWith(prefix)：搜尋是否存在以 prefix 開頭的單字

TrieNode 設計

每個節點只需要兩個屬性：children（子節點字典）和 is_end（是否為單字結尾）。

insert("app") 的過程

從 root 出發

root.children 沒有 "a"，建立新節點

root → a

移動到 a

a.children 沒有 "p"，建立新節點

root → a → p

移動到 p

p.children 沒有 "p"，建立新節點

root → a → p → p

—

字串走完

在最後的 p 節點設 is_end = True

p.is_end = ✓

implement_trie.py

class TrieNode:
    def __init__(self):
        self.children = {}   # char → TrieNode
        self.is_end = False  # 是否為某個單字的結尾


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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True   # 走完單字，標記結尾

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False   # 某個字元不存在，搜尋失敗
            node = node.children[ch]
        return node.is_end    # 走完還要確認是完整單字（非只是前綴）

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True           # 不管 is_end，只要前綴存在就 True


# 使用範例
trie = Trie()
trie.insert("apple")
trie.search("apple")    # True
trie.search("app")      # False（app 的 is_end=False）
trie.startsWith("app")  # True
trie.insert("app")
trie.search("app")      # True（insert 後 is_end=True）

⏱ Time: insert/search: O(L)💾 Space: O(ALPHABET × L × N)

search vs startsWith 的唯一差異

兩個函式的迴圈邏輯完全一樣，唯一差異是最後的回傳值：search 回傳 node.is_end（必須是完整單字），startsWith 直接回傳 True（只需前綴存在）。

🔍

Part 2 — Add and Search Words

#211 · Medium · 支援萬用字元 '.' 的 Trie

題目

設計一個支援 addWord(word) 和 search(word) 的資料結構。 search 中的 '.' 可以匹配任意一個字元。

addWord("bad"), addWord("dad"), addWord("mad")

search("pad") → False

search(".ad") → True（匹配 bad / dad / mad）

search("b..") → True（匹配 bad）

關鍵：遇到 '.' 要分支 DFS

一般字元走一條確定的路，但遇到 '.' 時，必須對當前節點所有的 children 都試一遍——這就是 DFS 回溯。任何一條路最終回傳 True，整體就是 True。

search(".ad") 的 DFS 過程（已 insert bad/dad/mad）

萬用字元，對 root 的所有 children（b, d, m）各走一遍

從 b 走 → b→a 存在；從 d 走 → d→a 存在；從 m 走 → m→a 存在

繼續走 → b→a→d.is_end=True ✅ 找到，回傳 True

add_and_search_words.py

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()   # 複用上面的 TrieNode

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        return self._dfs(word, 0, self.root)

    def _dfs(self, word: str, idx: int, node: TrieNode) -> bool:
        # 走完整個 word
        if idx == len(word):
            return node.is_end

        ch = word[idx]

        if ch == '.':
            # 萬用字元：對所有子節點遞迴嘗試
            for child in node.children.values():
                if self._dfs(word, idx + 1, child):
                    return True
            return False
        else:
            # 一般字元：走確定的路
            if ch not in node.children:
                return False
            return self._dfs(word, idx + 1, node.children[ch])

⏱ Time: addWord O(L)，search O(26^L) 最壞💾 Space: O(L × N)

最壞情況為什麼是 O(26^L)？

如果搜尋的是全部都是 '.'..'（全萬用字元），每個位置最多分支 26 次，深度為 L，所以是 O(26^L)。但實際情況下 Trie 裡的節點數有限，真正的複雜度接近 O(N × L)（N 為插入的單字數）。

🔄

Part 3 — Replace Words

#648 · Medium · 用最短前綴取代單字

題目

給一個字根（root）清單和一個句子。對句子中的每個單字，如果它以清單中某個字根開頭，就把它換成那個最短字根；否則保持不變。

dictionary = ["cat","bat","rat"]

sentence = "the cattle was rattled by the battery"

Output: "the cat was rat by the bat"

為什麼用 Trie 而不是 Set？

❌ 暴力法（Set）

對每個單字，從長度 1 開始逐一截前綴，查 set 看有沒有字根。假設單字最長 L，每次查詢 O(L²)，句子有 W 個單字，總體 O(W × L²)。

✅ Trie

把所有字根插入 Trie。搜尋時一個字元一個字元走，一旦遇到 is_end=True 就立刻停止，返回已走過的前綴。每個單字只需 O(L) 一次掃描。

搜尋 "cattle" 的過程（字根 Trie 中有 "cat"）

root.children["c"] 存在，移動

c_node.children["a"] 存在，移動

a_node.children["t"] 存在，移動，且 t_node.is_end = True ← 找到字根！

遇到 is_end=True 立刻停，回傳 "cat"，不再繼續往後走 "tle"。

replace_words.py

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

def replaceWords(dictionary: list[str], sentence: str) -> str:
    # Step 1：把所有字根插入 Trie
    root = TrieNode()
    for word in dictionary:
        node = root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    # Step 2：對句子每個單字，找最短字根前綴
    def find_root(word: str) -> str:
        node = root
        for i, ch in enumerate(word):
            if ch not in node.children:
                break                 # 沒有對應字根，保留原字
            node = node.children[ch]
            if node.is_end:
                return word[:i + 1]  # 找到字根，立刻回傳
        return word                   # 沒找到字根，原字不變

    return ' '.join(find_root(w) for w in sentence.split())

⏱ Time: O(D×L + S×L)💾 Space: O(D×L)

複雜度說明

D = 字根數，S = 句子單字數，L = 最長字串長度。建 Trie O(D×L)，每個單字查詢 O(L)，總查詢 O(S×L)，合計 O((D+S)×L)。

三題統一對比

題目	核心操作	特殊處理	查詢複雜度
#208 Implement Trie	insert / search / startsWith	search 需查 is_end，startsWith 不需要	O(L)
#211 Add and Search Words	addWord / search（含 '.'）	遇 '.' 分支 DFS 所有 children	O(26^L) 最壞
#648 Replace Words	建 Trie + 逐字查最短字根	遇 is_end 立刻停，回傳前綴	O(L) per word

什麼情況下要用 Trie？

→需要「前綴搜尋」或「自動補全」：Trie 是唯一直覺的選擇
→需要對大量字串做重複的前綴查詢：比 set 每次截前綴高效
→需要匹配萬用字元（.）：在 Trie 上做 DFS 比正則更可控
→題目提到 dictionary、word list、prefix：高機率是 Trie

這篇學到什麼

🌳Trie 的每個節點存 children（dict）和 is_end（bool），核心是「共享前綴」的樹狀結構

🏗️#208 基礎實作：insert 走完設 is_end=True；search 最後查 is_end；startsWith 直接回傳 True

🔍#211 遇到 "." 就對所有 children DFS，任何一條路 True 就回傳 True——這是 Trie + 回溯的組合拳

🔄#648 建好 Trie 後，逐字掃描遇 is_end 立刻停，O(L) 就找到最短字根，比逐一截前綴查 set 快

💡面試遇到「大量字串 + 前綴操作」，先考慮 Trie；遇到萬用字元搜尋，Trie + DFS 是標準解法

EP.18 — Monotonic Stack

Daily Temperatures、Trapping Rain Water

EP.20 — Heap

Kth Largest、Top K Frequent

LeetCode

Trie

前綴樹

DFS

字串搜尋

Python

EP.19

EP.19 — Trie：為字串搜尋而生的樹