交互式Python实验室

Trie (Prefix Tree)

Playground在加载时自动运行。点击运行我的代码来追踪你的Python代码 — 每一步实时动画展示。

解释·逐行

回放·逐步

挑战·引导式提示

XP·...

数据流水线

mastery 路径

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

解释

Line 1

Define TrieNode class

为什么用这种方法？

Each node holds children dict (maps char → TrieNode) and is_end flag (True if this node completes a word). This structure allows prefix sharing.

Structured Explanation

Overview

Trie(前缀树)将字符串存储在节点表示字符的树中，适合单词和前缀搜索。

Analogy

就像字典按字符分叉的树——知道"ca"就能快速找"cat"和"car"。

Step-by-step

每个节点有子节点字典和is_end标志
insert: 沿word[i]走，不存在则新建
search: 能走完全词且is_end为True
startsWith: 能走完前缀则True

Visual

insert("cat","car","dog") root / ... c d | | a o / \ \ t r g

Common mistakes

混淆search和startsWith的is_end差异
忘记删除操作很复杂

Practice questions

实现自动补全(前缀→候选词列表)
在字典中找最大XOR值的所有单词

Time

O(L) L为词长

Space

O(ALPHABET_SIZE * L * N)

复杂度

时间

O(m) — m = word length

空间

O(n × m) — n = words

复杂度概览

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

n = 8范围 1-20

当 N = 8 时

复杂度	操作
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

挑战

从['apple','app','apt','banana']构建Trie。实现search('app')和startsWith('ap')。

提示

每个节点是子节点的字典 + is_end标志。插入逐字符追踪，按需创建节点。

代码工作室

Trie (Prefix Tree)

Monaco就绪

Python就绪

lesson.pyline 1

Loading editor...

输出控制台

2 lines

❯ True

❯ False

现实世界应用

1

Search bar auto-complete

2

Network IP routing verification

3

Spellchecking dictionaries

Comments

Loading comments...