LeetCode Patterns ·

🎯 Trie

1️⃣ Core Framework

When discussing Trie, I frame it as:

What problem pattern Trie solves
Prefix-based search
Trie node structure
Insert operation
Search operation
StartsWith operation
Word termination marker
Trie vs HashSet
Common Trie problems
Senior-level explanation

2️⃣ What Problem Are We Solving?

Trie, also called a prefix tree, is used to store and search strings efficiently by prefix.

It is commonly used for:

Prefix search
Autocomplete
Dictionary word lookup
Word search
Replace words
Search suggestions
Longest word in dictionary
Design add and search words data structure
Word break optimization
IP routing conceptually
File system path matching
Prefix counting

The core idea is:

Each path from root represents a prefix.
Each complete path may represent a word.
Shared prefixes are stored only once.

👉 Interview Answer

A Trie is a tree-based data structure used to store strings by prefix.

Each node represents one character.

Words that share the same prefix also share the same path in the Trie.

Trie is especially useful for prefix search, autocomplete, dictionary lookup, and word search problems.

3️⃣ Why Trie Works

Suppose we insert:

cat
car
care
dog

The words cat, car, and care share the prefix:

ca

Trie stores the shared prefix only once.

Conceptually:

root
 ├── c
 │   └── a
 │       ├── t
 │       └── r
 │           └── e
 └── d
     └── o
         └── g

Key Insight

Instead of comparing full words repeatedly, Trie walks character by character.

For prefix lookup:

Does any word start with "ca"?

We only need to check whether the path exists.

👉 Interview Answer

Trie works because many strings share prefixes.

Instead of storing every word independently, Trie stores shared prefixes as shared paths.

Searching a word or prefix becomes a character-by-character traversal from the root.

4️⃣ Trie Node Structure

Basic Idea

Each Trie node usually contains:

children
is_word

Where:

children = mapping from character to child node
is_word = whether this node marks the end of a valid word

Python Node

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

Root Node

The root does not represent a character.

It is the starting point for all words.

root = TrieNode()

👉 Interview Answer

A Trie node usually stores a children map and a boolean end marker.

The children map points from a character to the next Trie node.

The end marker tells whether the current path forms a complete word.

5️⃣ Insert Operation

Purpose

insert(word) adds a word into the Trie.

For each character:

if character does not exist:
    create a new node

move to the child node

At the end:

mark is_word = True

Code

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

Example

Insert:

cat
car

Both words share:

c -> a

Then branch at:

t
r

👉 Interview Answer

To insert a word into a Trie, I start from the root and process one character at a time.

If the character path does not exist, I create a new Trie node.

After processing all characters, I mark the final node as the end of a valid word.

6️⃣ Search Operation

Purpose

search(word) checks whether a complete word exists in the Trie.

Important:

search("app") should return true only if "app" was inserted as a full word.

If only "apple" was inserted, then "app" is only a prefix, not necessarily a word.

Code

def search(self, word):
    node = self.root

    for char in word:
        if char not in node.children:
            return False

        node = node.children[char]

    return node.is_word

Why `is_word` Matters

If Trie contains:

apple

Then path exists for:

app

But unless app was inserted, search("app") should return:

False

👉 Interview Answer

Search walks through the Trie character by character.

If any character path is missing, the word does not exist.

After all characters are matched, I still need to check the end marker, because a prefix is not always a complete word.

7️⃣ StartsWith Operation

Purpose

startsWith(prefix) checks whether any word in the Trie starts with the given prefix.

Unlike search, it does not require is_word = True.

Code

def starts_with(self, prefix):
    node = self.root

    for char in prefix:
        if char not in node.children:
            return False

        node = node.children[char]

    return True

Example

If Trie contains:

apple

Then:

starts_with("app")  # True
search("app")       # False

Unless "app" was inserted as a full word.

👉 Interview Answer

StartsWith checks whether a prefix path exists in the Trie.

It does not need the final node to be marked as a word.

That is the key difference between prefix search and full-word search.

8️⃣ Complete Trie Template

Standard Template

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def search(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                return False

            node = node.children[char]

        return node.is_word

    def starts_with(self, prefix):
        node = self.root

        for char in prefix:
            if char not in node.children:
                return False

            node = node.children[char]

        return True

👉 Interview Answer

The standard Trie template has three main operations: insert, search, and startsWith.

Insert creates missing character nodes. Search checks both the path and the end marker. StartsWith only checks whether the prefix path exists.

9️⃣ Complexity Analysis

Let L Be Word Length

For insert:

Time: O(L)

For search:

Time: O(L)

For startsWith:

Time: O(L)

Space Complexity

For N words with average length L:

Worst-case space: O(N * L)

But Trie saves space when words share prefixes.

Important Interview Note

Trie is not always more memory-efficient than HashSet.

It can use more memory because each node stores a children map.

👉 Interview Answer

Trie operations are O(L), where L is the length of the word or prefix.

Space complexity is O(total characters inserted).

Trie can save space when many words share prefixes, but it may use more memory than a HashSet because each node stores child pointers.

🔟 Trie vs HashSet

HashSet

Good for:

exact word lookup
O(1) average lookup
simple dictionary membership

Trie

Good for:

prefix search
autocomplete
search suggestions
word search with pruning
finding words by shared prefix

Comparison

Pattern	Best For
HashSet	Exact word existence
Trie	Prefix-based search
Trie + DFS	Word search / autocomplete
HashSet + Prefix Set	Simpler prefix checking for small inputs

👉 Interview Answer

If the problem only asks whether a full word exists, a HashSet is usually simpler and faster.

If the problem asks for prefix search, autocomplete, search suggestions, or pruning during DFS, Trie is usually a better fit.

1️⃣1️⃣ Design Trie

Problem

Implement a Trie with:

insert
search
startsWith

Code

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def search(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                return False

            node = node.children[char]

        return node.is_word

    def startsWith(self, prefix):
        node = self.root

        for char in prefix:
            if char not in node.children:
                return False

            node = node.children[char]

        return True

👉 Interview Answer

For Design Trie, I use a root Trie node.

Each node has a children map and an is_word marker.

Insert creates missing nodes. Search checks whether the full word exists. StartsWith checks whether the prefix path exists.

1️⃣2️⃣ Add and Search Word

Problem

Design a data structure that supports:

addWord(word)
search(word)

But search may contain wildcard:

Where . can match any character.

Key Insight

Normal characters follow one path.

Wildcard . means:

try all children

This becomes DFS on the Trie.

Code

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


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

    def addWord(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def search(self, word):
        def dfs(index, node):
            if index == len(word):
                return node.is_word

            char = word[index]

            if char == ".":
                for child in node.children.values():
                    if dfs(index + 1, child):
                        return True

                return False

            if char not in node.children:
                return False

            return dfs(index + 1, node.children[char])

        return dfs(0, self.root)

👉 Interview Answer

For Add and Search Word, normal characters follow a single Trie path.

When I see a dot wildcard, I try all children from the current node using DFS.

At the end, I return true only if the final node is marked as a complete word.

1️⃣3️⃣ Word Search II

Problem

Given a board and a list of words, return all words that can be formed by adjacent cells.

Why Trie?

Brute force checks every word separately.

Trie allows DFS from the board while pruning invalid prefixes early.

Key Insight

During DFS:

current path must exist in Trie

If not:

stop immediately

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None


def find_words(board, words):
    root = TrieNode()

    for word in words:
        node = root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.word = word

    rows = len(board)
    cols = len(board[0])
    result = []

    def dfs(r, c, node):
        char = board[r][c]

        if char not in node.children:
            return

        next_node = node.children[char]

        if next_node.word:
            result.append(next_node.word)
            next_node.word = None

        board[r][c] = "#"

        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr = r + dr
            nc = c + dc

            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                dfs(nr, nc, next_node)

        board[r][c] = char

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)

    return result

👉 Interview Answer

Word Search II is a classic Trie plus DFS problem.

I first insert all words into a Trie.

Then I DFS from each board cell.

If the current board path is not a prefix in the Trie, I stop early.

This pruning avoids exploring many impossible paths.

1️⃣4️⃣ Replace Words

Problem

Given a dictionary of root words and a sentence, replace each word with the shortest root that is a prefix of the word.

Example:

dictionary = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"

Output:

"the cat was rat by the bat"

Trie Idea

Insert all root words into Trie.

For each sentence word, walk through Trie and stop at the first root word.

Code

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


def replace_words(dictionary, sentence):
    root = TrieNode()

    for word in dictionary:
        node = root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def find_root(word):
        node = root
        prefix = []

        for char in word:
            if char not in node.children:
                return word

            node = node.children[char]
            prefix.append(char)

            if node.is_word:
                return "".join(prefix)

        return word

    words = sentence.split()
    result = []

    for word in words:
        result.append(find_root(word))

    return " ".join(result)

👉 Interview Answer

For Replace Words, I insert all root words into a Trie.

For each word in the sentence, I walk character by character.

As soon as I reach a Trie node marked as a word, I return that prefix because we need the shortest root.

1️⃣5️⃣ Search Suggestions System

Problem

Given products and a search word, return up to 3 lexicographically smallest products after each character typed.

Approach 1: Sort + Binary Search

This is often simpler.

But Trie is also a valid approach.

Trie Idea

Insert products into Trie.

At each node, store up to 3 lexicographically smallest suggestions.

Because products are inserted in sorted order, each node can keep the first 3 words.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.suggestions = []


def suggested_products(products, search_word):
    products.sort()
    root = TrieNode()

    for product in products:
        node = root

        for char in product:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

            if len(node.suggestions) < 3:
                node.suggestions.append(product)

    result = []
    node = root

    for char in search_word:
        if node and char in node.children:
            node = node.children[char]
            result.append(node.suggestions)
        else:
            node = None
            result.append([])

    return result

👉 Interview Answer

For Search Suggestions, I can use a Trie where each node stores up to three suggestions for that prefix.

If I insert products in sorted order, the first three products stored at each prefix node are already lexicographically smallest.

Then each typed character just moves one level deeper in the Trie.

1️⃣6️⃣ Longest Word in Dictionary

Problem

Find the longest word that can be built one character at a time by other words in the dictionary.

Example:

["w", "wo", "wor", "worl", "world"]

Answer:

world

Trie Idea

A valid word can only continue through nodes where every prefix is also a word.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None


def longest_word(words):
    root = TrieNode()

    for word in words:
        node = root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.word = word

    result = ""

    def dfs(node):
        nonlocal result

        if node != root and node.word is None:
            return

        if node.word:
            if len(node.word) > len(result) or (
                len(node.word) == len(result) and node.word < result
            ):
                result = node.word

        for char in sorted(node.children.keys()):
            dfs(node.children[char])

    dfs(root)
    return result

👉 Interview Answer

For Longest Word in Dictionary, I use Trie to represent all words.

During DFS, I only continue through nodes that represent valid words.

This guarantees every prefix of the candidate word exists in the dictionary.

1️⃣7️⃣ Prefix Count

Problem

Count how many words start with a given prefix.

Trie Enhancement

Add a counter to each Trie node:

prefix_count

Every time a word passes through a node, increment the counter.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.prefix_count = 0


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]
            node.prefix_count += 1

        node.is_word = True

    def count_prefix(self, prefix):
        node = self.root

        for char in prefix:
            if char not in node.children:
                return 0

            node = node.children[char]

        return node.prefix_count

👉 Interview Answer

To count words with a prefix, I store a prefix count at each Trie node.

During insertion, every node on the word path increments its prefix count.

Then counting words with a prefix is just walking to the prefix node and returning its count.

1️⃣8️⃣ Delete Word from Trie

Problem

Remove a word from Trie.

Important Cases

When deleting a word:

The word may be a prefix of another word.
The word may share prefix with other words.
Only unused nodes should be removed.

Code

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def delete(self, word):
        def dfs(node, index):
            if index == len(word):
                if not node.is_word:
                    return False

                node.is_word = False
                return len(node.children) == 0

            char = word[index]

            if char not in node.children:
                return False

            should_delete_child = dfs(node.children[char], index + 1)

            if should_delete_child:
                del node.children[char]

                return not node.is_word and len(node.children) == 0

            return False

        dfs(self.root, 0)

👉 Interview Answer

Deleting from a Trie requires care because nodes may be shared by other words.

I first unmark the final word node.

Then I remove nodes only if they have no children and are not the end of another word.

This preserves shared prefixes used by other words.

1️⃣9️⃣ Trie with Array Children

Dictionary Children

Most Python solutions use:

children = {}

This is flexible and works for any character set.

Array Children

If input only contains lowercase English letters, we can use:

children = [None] * 26

Code

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_word = False


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

    def insert(self, word):
        node = self.root

        for char in word:
            index = ord(char) - ord("a")

            if node.children[index] is None:
                node.children[index] = TrieNode()

            node = node.children[index]

        node.is_word = True

    def search(self, word):
        node = self.root

        for char in word:
            index = ord(char) - ord("a")

            if node.children[index] is None:
                return False

            node = node.children[index]

        return node.is_word

Comparison

Children Type	Best For
Dictionary	Flexible character set
Array of 26	Lowercase English letters
Dictionary	Usually simpler in Python
Array	Slightly faster indexing, fixed alphabet

👉 Interview Answer

In Python, I usually use a dictionary for Trie children because it is simple and flexible.

If the problem guarantees only lowercase English letters, an array of size 26 is also possible.

The array version has fixed alphabet assumptions, while the dictionary version works for more general inputs.

2️⃣0️⃣ Trie vs DFS / Backtracking

DFS / Backtracking Alone

Good for:

exploring combinations
searching board paths
generating candidates

But it may explore many invalid paths.

Trie + DFS

Good for:

word search
prefix pruning
dictionary-guided backtracking
autocomplete traversal

Key Difference

DFS explores possibilities.

Trie tells whether the current path is still valid.

Together:

DFS generates paths.
Trie prunes invalid prefixes.

👉 Interview Answer

Trie is often combined with DFS or backtracking.

DFS explores possible paths, while Trie checks whether the current path is a valid prefix.

This allows us to prune impossible branches early, which is especially useful in Word Search II.

2️⃣1️⃣ Common Edge Cases

Empty String

Some problems allow:

""

Need to decide whether root can be marked as a word.

Word Is Prefix of Another Word

Example:

app
apple

Both can exist.

Need is_word to distinguish them.

Duplicate Inserts

Inserting the same word multiple times may require:

word count

instead of boolean.

Character Set

Input may include:

lowercase letters
uppercase letters
digits
symbols
unicode characters

Dictionary children handle this more easily.

Wildcard Search

For wildcard .:

must DFS all children

👉 Interview Answer

Common Trie edge cases include empty strings, words that are prefixes of other words, duplicate inserted words, character set assumptions, and wildcard search.

The is_word marker is important because prefix existence and word existence are different concepts.

2️⃣2️⃣ Common Mistakes

Mistake 1: Forgetting `is_word`

Wrong:

return True

after matching all characters.

Correct:

return node.is_word

Mistake 2: Treating Prefix as Word

If only "apple" exists:

search("app")

should usually return:

False

Mistake 3: Not Pruning in Word Search II

Without Trie prefix pruning, DFS becomes much more expensive.

Mistake 4: Returning Duplicate Words

In Word Search II, after finding a word, mark it as used:

node.word = None

Mistake 5: Assuming Only Lowercase Letters

Array children only works if alphabet is fixed.

Mistake 6: Deleting Shared Prefix Nodes Incorrectly

Do not delete nodes still used by another word.

👉 Interview Answer

Common Trie mistakes include forgetting the end marker, confusing prefix existence with word existence, not pruning DFS using Trie, returning duplicate words, assuming the wrong character set, and deleting shared prefix nodes incorrectly.

2️⃣3️⃣ When Trie Applies

Good Fit

Use Trie when the problem asks for:

prefix search
autocomplete
dictionary lookup by prefix
search suggestions
word search with pruning
startsWith queries
many strings sharing prefixes
wildcard dictionary search

Problem Signals

Look for words like:

prefix
starts with
autocomplete
dictionary
word search
suggestions
replace words
root word
wildcard
search word

👉 Interview Answer

I consider Trie when the problem is about strings and prefixes.

Common signals include prefix search, autocomplete, search suggestions, dictionary lookup, replace words, wildcard word search, and board word search with prefix pruning.

2️⃣4️⃣ When Trie Does Not Apply

Not Good Fit

Trie may not be ideal when:

only exact word lookup is needed
small number of strings
no prefix queries
memory is very constrained
sorting or HashSet is simpler

Better Alternatives

Problem Type	Better Pattern
Exact word existence	HashSet
Sort words lexicographically	Sorting
Find substring in one large text	KMP / Rabin-Karp / suffix structures
Small input prefix check	HashSet of prefixes
Search suggestions from sorted list	Binary search

👉 Interview Answer

Trie is not always necessary.

If the problem only needs exact word lookup, HashSet is simpler.

If the input is small, a direct scan may be enough.

Trie is most useful when prefix queries are frequent or when prefix pruning significantly reduces search space.

2️⃣5️⃣ Standard Templates

Basic Trie Template

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def search(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                return False

            node = node.children[char]

        return node.is_word

    def starts_with(self, prefix):
        node = self.root

        for char in prefix:
            if char not in node.children:
                return False

            node = node.children[char]

        return True

Trie With Word Storage

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

Useful for:

Word Search II
Returning actual matched word
Avoiding rebuilding path string

Trie With Prefix Count

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.prefix_count = 0
        self.word_count = 0

Useful for:

countWordsStartingWith
countWordsEqualTo
erase

Wildcard Trie Search Template

def search(word):
    def dfs(index, node):
        if index == len(word):
            return node.is_word

        char = word[index]

        if char == ".":
            for child in node.children.values():
                if dfs(index + 1, child):
                    return True

            return False

        if char not in node.children:
            return False

        return dfs(index + 1, node.children[char])

    return dfs(0, root)

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

A Trie, also called a prefix tree, is a tree-based data structure used to store strings by prefix.

Each node represents one character on a path from the root. Words that share prefixes also share the same Trie path.

A Trie node usually stores a children map and an end marker. The children map points from character to child node. The end marker tells whether the current path forms a complete word.

Insert starts from the root and processes the word character by character. If a character path does not exist, we create a new node. After all characters are inserted, we mark the final node as a word.

Search also walks character by character. If any character is missing, the word does not exist. After all characters are matched, we must check the end marker, because a prefix is not necessarily a complete word.

StartsWith is similar to search, but it only checks whether the prefix path exists. It does not require the final node to be marked as a word.

The time complexity of insert, search, and startsWith is O(L), where L is the length of the word or prefix. Space complexity is O(total characters inserted), although shared prefixes reduce duplicated storage.

Compared with HashSet, Trie is not usually needed for exact word lookup. HashSet is simpler for checking whether a full word exists. Trie becomes valuable when the problem needs prefix search, autocomplete, search suggestions, or prefix pruning during DFS.

Common Trie problems include Design Trie, Add and Search Word with wildcard, Word Search II, Replace Words, Search Suggestions System, Longest Word in Dictionary, and prefix counting.

In Word Search II, Trie is powerful because DFS can stop immediately when the current board path is not a valid prefix. This avoids exploring many invalid paths.

In wildcard search, normal characters follow one path, while a dot wildcard means we must try all children using DFS.

At a senior level, I would explain: what each Trie node represents, why shared prefixes matter, why is_word is necessary, how insert, search, and startsWith differ, when Trie is better than HashSet, and how Trie can combine with DFS to prune search space.

⭐ Final Insight

Trie 的核心不是“children map 模板”。

它的核心是利用 shared prefix 来组织字符串。

Senior-level 的重点是：

node 代表什么， path 代表什么， is_word 为什么必须存在， search 和 startsWith 的区别，为什么 Trie 适合 prefix query，什么时候 HashSet 更简单，以及 Trie 如何和 DFS 结合做 prefix pruning。

能讲清楚这些， Trie 就是一种处理 prefix search、autocomplete、dictionary lookup 和 word search 的核心数据结构。

中文部分

🎯 Trie

1️⃣ 核心框架

讨论 Trie 时，我通常从：

Trie 解决什么问题
Prefix-based search
Trie node structure
Insert operation
Search operation
StartsWith operation
Word termination marker
Trie vs HashSet
常见 Trie 问题
高级工程师解释方式

2️⃣ 要解决什么问题？

Trie，也叫 prefix tree，用于高效存储和查询字符串前缀。

它常用于：

Prefix search
Autocomplete
Dictionary word lookup
Word search
Replace words
Search suggestions
Longest word in dictionary
Design add and search words data structure
Word break optimization
IP routing conceptually
File system path matching
Prefix counting

核心思想是：

从 root 到某个 node 的路径代表一个 prefix。
某些完整路径代表一个 word。
共享 prefix 的 words 会共享同一段路径。

👉 面试回答

Trie 是一种基于 tree 的字符串数据结构，用来按照 prefix 存储字符串。

每个 node 通常代表一个 character。

拥有相同 prefix 的 words，会共享 Trie 中相同的路径。

Trie 特别适合 prefix search、autocomplete、 dictionary lookup 和 word search 类问题。

3️⃣ 为什么 Trie 有效？

假设插入：

cat
car
care
dog

cat、car 和 care 共享 prefix：

ca

Trie 只会存储一次这个 shared prefix。

概念上：

root
 ├── c
 │   └── a
 │       ├── t
 │       └── r
 │           └── e
 └── d
     └── o
         └── g

Key Insight

Trie 不需要反复比较完整字符串。

它是按 character 一层一层走。

对于 prefix 查询：

有没有 word 以 "ca" 开头？

只需要看这条 path 是否存在。

👉 面试回答

Trie 有效的原因是很多字符串会共享 prefix。

Trie 不把每个 word 完全独立存储，而是把 shared prefix 存成 shared path。

搜索 word 或 prefix 时，只需要从 root 开始逐字符遍历。

4️⃣ Trie Node Structure

Basic Idea

每个 Trie node 通常包含：

children
is_word

其中：

children = character 到 child node 的映射
is_word = 当前 path 是否构成一个完整 word

Python Node

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

Root Node

Root 本身不代表任何 character。

它是所有 word 的起点。

root = TrieNode()

👉 面试回答

Trie node 通常包含一个 children map 和一个 end marker。

children map 表示从当前 node 可以走向哪些 characters。

end marker 用来表示当前 path 是否是一个完整 word。

5️⃣ Insert Operation

Purpose

insert(word) 把一个 word 加入 Trie。

对每个 character：

如果 character path 不存在：
    创建一个新的 node

移动到 child node

最后：

标记 is_word = True

Code

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

Example

插入：

cat
car

两个 words 共享：

c -> a

然后在这里分叉：

t
r

👉 面试回答

插入一个 word 时，我从 root 开始逐字符处理。

如果当前 character 的 path 不存在，就创建一个新的 Trie node。

当所有 characters 都处理完之后，把最后一个 node 标记为完整 word 的结尾。

6️⃣ Search Operation

Purpose

search(word) 判断一个完整 word 是否存在于 Trie 中。

注意：

search("app") 只有在 "app" 被完整插入时才应该返回 true。

如果只插入了 "apple"，那么 "app" 只是 prefix，不一定是完整 word。

Code

def search(self, word):
    node = self.root

    for char in word:
        if char not in node.children:
            return False

        node = node.children[char]

    return node.is_word

Why `is_word` Matters

如果 Trie 中有：

apple

那么确实存在 path：

app

但是如果没有插入 "app"， search("app") 应该返回：

False

👉 面试回答

Search 会从 root 开始逐字符遍历 Trie。

如果某个 character path 不存在，说明 word 不存在。

即使所有 characters 都匹配了，最后也必须检查 is_word，因为 prefix 不一定是完整 word。

7️⃣ StartsWith Operation

Purpose

startsWith(prefix) 判断 Trie 中是否存在某个 word 以该 prefix 开头。

和 search 不同，它不要求 is_word = True。

Code

def starts_with(self, prefix):
    node = self.root

    for char in prefix:
        if char not in node.children:
            return False

        node = node.children[char]

    return True

Example

如果 Trie 中有：

apple

那么：

starts_with("app")  # True
search("app")       # False

除非 "app" 也被完整插入。

👉 面试回答

StartsWith 只检查 prefix path 是否存在。

它不要求最后一个 node 是完整 word 的结尾。

这就是 prefix search 和 full-word search 的核心区别。

8️⃣ 完整 Trie 模板

Standard Template

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def search(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                return False

            node = node.children[char]

        return node.is_word

    def starts_with(self, prefix):
        node = self.root

        for char in prefix:
            if char not in node.children:
                return False

            node = node.children[char]

        return True

👉 面试回答

标准 Trie 模板主要有三个操作： insert、search 和 startsWith。

Insert 用来创建缺失的 character nodes。 Search 要同时检查 path 和 end marker。 StartsWith 只检查 prefix path 是否存在。

9️⃣ Complexity Analysis

假设 L 是 word 长度

Insert:

Time: O(L)

Search:

Time: O(L)

StartsWith:

Time: O(L)

Space Complexity

对于 N 个 words，平均长度为 L：

Worst-case space: O(N * L)

但是如果很多 words 共享 prefix， Trie 可以减少重复 prefix 的存储。

Important Interview Note

Trie 不一定比 HashSet 更省内存。

因为每个 Trie node 都可能需要存 children map。

👉 面试回答

Trie 的 insert、search 和 startsWith 都是 O(L)，其中 L 是 word 或 prefix 的长度。

Space complexity 是 O(total characters inserted)。

当很多 words 共享 prefix 时， Trie 可以减少重复存储。

但 Trie 不一定比 HashSet 更省内存，因为每个 node 都要维护 children pointers。

🔟 Trie vs HashSet

HashSet

适合：

exact word lookup
O(1) average lookup
simple dictionary membership

Trie

适合：

prefix search
autocomplete
search suggestions
word search with pruning
finding words by shared prefix

Comparison

Pattern	Best For
HashSet	Exact word existence
Trie	Prefix-based search
Trie + DFS	Word search / autocomplete
HashSet + Prefix Set	小输入下的简单 prefix checking

👉 面试回答

如果题目只问一个完整 word 是否存在， HashSet 通常更简单。

如果题目涉及 prefix search、autocomplete、 search suggestions，或者 DFS 中需要 prefix pruning， Trie 通常更合适。

1️⃣1️⃣ Design Trie

Problem

实现一个 Trie，支持：

insert
search
startsWith

Code

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def search(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                return False

            node = node.children[char]

        return node.is_word

    def startsWith(self, prefix):
        node = self.root

        for char in prefix:
            if char not in node.children:
                return False

            node = node.children[char]

        return True

👉 面试回答

Design Trie 中，我会使用一个 root Trie node。

每个 node 有 children map 和 is_word marker。

Insert 创建缺失的 nodes。 Search 判断完整 word 是否存在。 StartsWith 判断 prefix path 是否存在。

1️⃣2️⃣ Add and Search Word

Problem

设计一个数据结构，支持：

addWord(word)
search(word)

但是 search 中可能包含 wildcard：

. 可以匹配任意 character。

Key Insight

普通 character 只走一条 path。

Wildcard . 表示：

尝试所有 children

这会变成 Trie 上的 DFS。

Code

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


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

    def addWord(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def search(self, word):
        def dfs(index, node):
            if index == len(word):
                return node.is_word

            char = word[index]

            if char == ".":
                for child in node.children.values():
                    if dfs(index + 1, child):
                        return True

                return False

            if char not in node.children:
                return False

            return dfs(index + 1, node.children[char])

        return dfs(0, self.root)

👉 面试回答

Add and Search Word 中，普通 character 只需要沿着一条 Trie path 走。

当遇到 dot wildcard 时，需要用 DFS 尝试当前 node 的所有 children。

最后只有到达完整 word 的 end marker，才返回 true。

1️⃣3️⃣ Word Search II

Problem

给定一个 board 和一个 words list，返回所有可以由相邻 cells 组成的 words。

Why Trie?

Brute force 会逐个 word 去 board 中搜索。

Trie 可以在 board DFS 时做 prefix pruning。

Key Insight

DFS 过程中：

current path 必须是 Trie 中的一个 prefix

否则：

立即停止

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None


def find_words(board, words):
    root = TrieNode()

    for word in words:
        node = root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.word = word

    rows = len(board)
    cols = len(board[0])
    result = []

    def dfs(r, c, node):
        char = board[r][c]

        if char not in node.children:
            return

        next_node = node.children[char]

        if next_node.word:
            result.append(next_node.word)
            next_node.word = None

        board[r][c] = "#"

        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr = r + dr
            nc = c + dc

            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                dfs(nr, nc, next_node)

        board[r][c] = char

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)

    return result

👉 面试回答

Word Search II 是经典的 Trie + DFS 问题。

我先把所有 words 插入 Trie。

然后从 board 的每个 cell 开始 DFS。

如果当前 path 在 Trie 中不是一个 prefix，就立即停止。

这个 prefix pruning 可以避免大量无效搜索。

1️⃣4️⃣ Replace Words

Problem

给定 root words dictionary 和一个 sentence，把 sentence 中的每个 word 替换成最短 root prefix。

Example:

dictionary = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"

Output:

"the cat was rat by the bat"

Trie Idea

把所有 root words 插入 Trie。

对 sentence 中每个 word，在 Trie 中逐字符走，遇到第一个 root word 就停止。

Code

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


def replace_words(dictionary, sentence):
    root = TrieNode()

    for word in dictionary:
        node = root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def find_root(word):
        node = root
        prefix = []

        for char in word:
            if char not in node.children:
                return word

            node = node.children[char]
            prefix.append(char)

            if node.is_word:
                return "".join(prefix)

        return word

    words = sentence.split()
    result = []

    for word in words:
        result.append(find_root(word))

    return " ".join(result)

👉 面试回答

Replace Words 中，我先把所有 root words 插入 Trie。

对 sentence 中每个 word，从 root 开始逐字符查找。

一旦遇到 is_word 为 true 的 node，就返回当前 prefix，因为题目要求最短 root。

1️⃣5️⃣ Search Suggestions System

Problem

给定 products 和 search word，每输入一个 character，返回最多 3 个字典序最小的 matching products。

Approach 1: Sort + Binary Search

这题也可以用 sort + binary search，通常代码更简单。

但 Trie 也是一个合理解法。

Trie Idea

把 products 插入 Trie。

每个 node 存最多 3 个 lexicographically smallest suggestions。

因为 products 已经排序，插入时每个 prefix node 保留前 3 个即可。

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.suggestions = []


def suggested_products(products, search_word):
    products.sort()
    root = TrieNode()

    for product in products:
        node = root

        for char in product:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

            if len(node.suggestions) < 3:
                node.suggestions.append(product)

    result = []
    node = root

    for char in search_word:
        if node and char in node.children:
            node = node.children[char]
            result.append(node.suggestions)
        else:
            node = None
            result.append([])

    return result

👉 面试回答

Search Suggestions 可以用 Trie。

每个 Trie node 存当前 prefix 对应的最多 3 个 suggestions。

如果 products 按字典序插入，每个 node 最先存进去的 3 个 products，就是这个 prefix 下字典序最小的 3 个结果。

查询时每输入一个 character，向 Trie 下一层移动即可。

1️⃣6️⃣ Longest Word in Dictionary

Problem

找到最长的 word，并且这个 word 可以通过 dictionary 中其他 words 一步步构建出来。

Example:

["w", "wo", "wor", "worl", "world"]

Answer:

world

Trie Idea

一个 word 合法的前提是：

它的每个 prefix 都必须是 word

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None


def longest_word(words):
    root = TrieNode()

    for word in words:
        node = root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.word = word

    result = ""

    def dfs(node):
        nonlocal result

        if node != root and node.word is None:
            return

        if node.word:
            if len(node.word) > len(result) or (
                len(node.word) == len(result) and node.word < result
            ):
                result = node.word

        for char in sorted(node.children.keys()):
            dfs(node.children[char])

    dfs(root)
    return result

👉 面试回答

Longest Word in Dictionary 可以用 Trie。

我把所有 words 插入 Trie。

DFS 的时候，只有当前 node 本身代表一个 valid word，才继续向下走。

这样可以保证 candidate word 的每个 prefix 都存在于 dictionary 中。

1️⃣7️⃣ Prefix Count

Problem

统计有多少 words 以某个 prefix 开头。

Trie Enhancement

在每个 Trie node 上增加：

prefix_count

每次插入 word 经过某个 node，就把这个 node 的 prefix_count 加一。

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.prefix_count = 0


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]
            node.prefix_count += 1

        node.is_word = True

    def count_prefix(self, prefix):
        node = self.root

        for char in prefix:
            if char not in node.children:
                return 0

            node = node.children[char]

        return node.prefix_count

👉 面试回答

要统计某个 prefix 下有多少 words，可以在每个 Trie node 存 prefix_count。

插入 word 时，每经过一个 node，就增加它的 prefix_count。

查询时只需要走到 prefix 对应的 node，返回这个 node 的 prefix_count。

1️⃣8️⃣ Delete Word from Trie

Problem

从 Trie 中删除一个 word。

Important Cases

删除 word 时需要注意：

这个 word 可能是另一个 word 的 prefix。
这个 word 可能和其他 words 共享 prefix。
只能删除已经不被其他 words 使用的 nodes。

Code

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def delete(self, word):
        def dfs(node, index):
            if index == len(word):
                if not node.is_word:
                    return False

                node.is_word = False
                return len(node.children) == 0

            char = word[index]

            if char not in node.children:
                return False

            should_delete_child = dfs(node.children[char], index + 1)

            if should_delete_child:
                del node.children[char]

                return not node.is_word and len(node.children) == 0

            return False

        dfs(self.root, 0)

👉 面试回答

Trie 删除操作要小心，因为很多 nodes 可能被多个 words 共享。

我会先取消最后一个 node 的 is_word 标记。

然后只有当某个 node 没有 children，并且它不是另一个 word 的结尾时，才可以删除它。

这样不会破坏其他共享 prefix 的 words。

1️⃣9️⃣ Trie with Array Children

Dictionary Children

Python 中常用：

children = {}

这种方式灵活，适合不同 character set。

Array Children

如果题目保证只有 lowercase English letters，可以使用：

children = [None] * 26

Code

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_word = False


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

    def insert(self, word):
        node = self.root

        for char in word:
            index = ord(char) - ord("a")

            if node.children[index] is None:
                node.children[index] = TrieNode()

            node = node.children[index]

        node.is_word = True

    def search(self, word):
        node = self.root

        for char in word:
            index = ord(char) - ord("a")

            if node.children[index] is None:
                return False

            node = node.children[index]

        return node.is_word

Comparison

Children Type	Best For
Dictionary	Flexible character set
Array of 26	Lowercase English letters
Dictionary	Python 中通常更简单
Array	固定 alphabet 下 indexing 稍快

👉 面试回答

Python 中我通常用 dictionary 存 Trie children，因为更简单也更灵活。

如果题目明确只有 lowercase English letters，也可以用长度为 26 的 array。

Array version 对 alphabet 有固定假设， dictionary version 更通用。

2️⃣0️⃣ Trie vs DFS / Backtracking

DFS / Backtracking Alone

适合：

exploring combinations
searching board paths
generating candidates

但可能会探索大量无效路径。

Trie + DFS

适合：

word search
prefix pruning
dictionary-guided backtracking
autocomplete traversal

Key Difference

DFS 负责探索可能路径。

Trie 判断当前路径是否还可能有效。

结合起来：

DFS generates paths.
Trie prunes invalid prefixes.

👉 面试回答

Trie 经常和 DFS 或 backtracking 一起使用。

DFS 负责探索路径， Trie 负责判断当前路径是否是一个 valid prefix。

如果当前 prefix 不存在于 Trie 中，就可以提前停止搜索。

这在 Word Search II 中非常典型。

2️⃣1️⃣ 常见 Edge Cases

Empty String

有些题可能允许：

""

这时要决定 root 是否可以被标记为 word。

Word Is Prefix of Another Word

Example:

app
apple

两个都可以存在。

必须用 is_word 区分它们。

Duplicate Inserts

如果同一个 word 被插入多次，可能需要：

word count

而不是 boolean。

Character Set

输入可能包含：

lowercase letters
uppercase letters
digits
symbols
unicode characters

Dictionary children 更容易处理这些情况。

Wildcard Search

遇到 wildcard .：

必须 DFS 所有 children

👉 面试回答

Trie 常见 edge cases 包括 empty string、一个 word 是另一个 word 的 prefix、 duplicate inserts、 character set assumptions、以及 wildcard search。

is_word 很重要，因为 prefix 存在和 word 存在是两个不同概念。

2️⃣2️⃣ 常见错误

Mistake 1: 忘记 `is_word`

错误：

return True

当所有 characters 匹配后直接返回 True。

正确：

return node.is_word

Mistake 2: 把 Prefix 当成 Word

如果只插入了 "apple"：

search("app")

通常应该返回：

False

Mistake 3: Word Search II 中没有 Pruning

如果不用 Trie 做 prefix pruning， DFS 会非常贵。

Mistake 4: 返回重复 Words

Word Search II 中，找到 word 后可以标记：

node.word = None

避免重复返回。

Mistake 5: 错误假设只有 Lowercase Letters

Array children 只有在 alphabet 固定时才安全。

Mistake 6: 删除 Shared Prefix Nodes

删除 Trie node 时，不能删除仍然被其他 words 使用的 shared prefix。

👉 面试回答

Trie 常见错误包括：忘记 end marker、混淆 prefix existence 和 word existence、 Word Search II 中没有用 Trie pruning、返回重复 words、错误假设 character set，以及删除 shared prefix nodes 时破坏其他 words。

2️⃣3️⃣ 什么时候 Trie 适用？

Good Fit

当题目问：

prefix search
autocomplete
dictionary lookup by prefix
search suggestions
word search with pruning
startsWith queries
many strings sharing prefixes
wildcard dictionary search

Problem Signals

看到这些关键词想到 Trie：

prefix
starts with
autocomplete
dictionary
word search
suggestions
replace words
root word
wildcard
search word

👉 面试回答

当问题和 strings + prefixes 有关时，我会考虑 Trie。

常见信号包括 prefix search、autocomplete、 search suggestions、dictionary lookup、 replace words、wildcard word search，以及 board word search with prefix pruning。

2️⃣4️⃣ 什么时候 Trie 不适用？

Not Good Fit

Trie 不一定适合：

only exact word lookup is needed
small number of strings
no prefix queries
memory is very constrained
sorting or HashSet is simpler

Better Alternatives

Problem Type	Better Pattern
Exact word existence	HashSet
Sort words lexicographically	Sorting
Find substring in one large text	KMP / Rabin-Karp / suffix structures
Small input prefix check	HashSet of prefixes
Search suggestions from sorted list	Binary search

👉 面试回答

Trie 不是所有 string 问题都需要用。

如果只是 exact word lookup， HashSet 更简单。

如果输入很小，直接扫描可能就够了。

Trie 最适合 frequent prefix queries，或者 prefix pruning 能明显减少搜索空间的场景。

2️⃣5️⃣ 标准模板

Basic Trie Template

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


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

    def insert(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()

            node = node.children[char]

        node.is_word = True

    def search(self, word):
        node = self.root

        for char in word:
            if char not in node.children:
                return False

            node = node.children[char]

        return node.is_word

    def starts_with(self, prefix):
        node = self.root

        for char in prefix:
            if char not in node.children:
                return False

            node = node.children[char]

        return True

Trie With Word Storage

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

适合：

Word Search II
Returning actual matched word
Avoiding rebuilding path string

Trie With Prefix Count

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.prefix_count = 0
        self.word_count = 0

适合：

countWordsStartingWith
countWordsEqualTo
erase

Wildcard Trie Search Template

def search(word):
    def dfs(index, node):
        if index == len(word):
            return node.is_word

        char = word[index]

        if char == ".":
            for child in node.children.values():
                if dfs(index + 1, child):
                    return True

            return False

        if char not in node.children:
            return False

        return dfs(index + 1, node.children[char])

    return dfs(0, root)

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Trie，也叫 prefix tree，是一种基于 tree 的数据结构，用来按 prefix 存储字符串。

每个 node 代表从 root 到当前路径中的一个 character。拥有相同 prefix 的 words，会共享 Trie 中的同一条路径。

一个 Trie node 通常包含 children map 和 end marker。 children map 表示 character 到 child node 的映射。 end marker 表示当前 path 是否构成一个完整 word。

Insert 从 root 开始，逐字符处理 word。如果 character path 不存在，就创建一个新的 node。所有 characters 处理完后，把最后一个 node 标记为 word。

Search 也是逐字符遍历。如果某个 character path 不存在， word 就不存在。即使所有 characters 都匹配，最后也必须检查 end marker，因为 prefix 不一定是完整 word。

StartsWith 和 search 类似，但它只检查 prefix path 是否存在，不要求最后一个 node 被标记为 word。

Trie 的 insert、search 和 startsWith 时间复杂度都是 O(L)，其中 L 是 word 或 prefix 的长度。空间复杂度是 O(total characters inserted)，但 shared prefix 可以减少重复存储。

和 HashSet 相比，如果只是 exact word lookup， Trie 通常不是必须的。 HashSet 更简单。但如果问题涉及 prefix search、autocomplete、 search suggestions，或 DFS 中的 prefix pruning， Trie 会更合适。

常见 Trie 问题包括 Design Trie、 Add and Search Word with wildcard、 Word Search II、 Replace Words、 Search Suggestions System、 Longest Word in Dictionary，以及 prefix counting。

在 Word Search II 中， Trie 很有用，因为 DFS 时一旦发现当前 board path 不是 valid prefix，就可以立即停止搜索。这可以避免大量无效路径。

在 wildcard search 中，普通 character 只走一条 path，而 dot wildcard 需要尝试当前 node 的所有 children。

高级工程师解释 Trie 时，我会讲清楚：每个 Trie node 代表什么， shared prefix 为什么重要， is_word 为什么必须存在， insert、search 和 startsWith 的区别， Trie 什么时候比 HashSet 更合适，以及 Trie 如何结合 DFS 做 search-space pruning。

⭐ Final Insight

Trie 的核心不是“children map 模板”。

它的核心是利用 shared prefix 来组织字符串。

Senior-level 的重点是：

node 代表什么， path 代表什么， is_word 为什么必须存在， search 和 startsWith 的区别，为什么 Trie 适合 prefix query，什么时候 HashSet 更简单，以及 Trie 如何和 DFS 结合做 prefix pruning。

能讲清楚这些， Trie 就是一种处理 prefix search、autocomplete、dictionary lookup 和 word search 的核心数据结构。

🎯 Trie

1️⃣ Core Framework

2️⃣ What Problem Are We Solving?

3️⃣ Why Trie Works

Prefix Sharing

Key Insight

4️⃣ Trie Node Structure

Basic Idea

Python Node

Root Node

5️⃣ Insert Operation

Purpose

Code

Example

6️⃣ Search Operation

Purpose

Code

Why is_word Matters

7️⃣ StartsWith Operation

Purpose

Code

Example

8️⃣ Complete Trie Template

Standard Template

9️⃣ Complexity Analysis

Let L Be Word Length

Space Complexity

Important Interview Note

🔟 Trie vs HashSet

HashSet

Trie

Comparison

1️⃣1️⃣ Design Trie

Problem

Code

1️⃣2️⃣ Add and Search Word

Problem

Key Insight

Code

1️⃣3️⃣ Word Search II

Problem

Why Trie?

Key Insight

Code

1️⃣4️⃣ Replace Words

Problem

Trie Idea

Code

1️⃣5️⃣ Search Suggestions System

Problem

Approach 1: Sort + Binary Search

Trie Idea

Code

1️⃣6️⃣ Longest Word in Dictionary

Problem

Trie Idea

Code

1️⃣7️⃣ Prefix Count

Problem

Trie Enhancement

Code

1️⃣8️⃣ Delete Word from Trie

Problem

Important Cases

Code

1️⃣9️⃣ Trie with Array Children

Dictionary Children

Array Children

Code

Comparison

2️⃣0️⃣ Trie vs DFS / Backtracking

DFS / Backtracking Alone

Trie + DFS

Key Difference

2️⃣1️⃣ Common Edge Cases

Empty String

Word Is Prefix of Another Word

Duplicate Inserts

Character Set

Wildcard Search

Why `is_word` Matters

Mistake 1: Forgetting `is_word`

Why `is_word` Matters