208. 实现 Trie (前缀树)

力扣题目链接 (opens new window)

题目描述

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次

思路

Trie（前缀树/字典树）是一种专门处理字符串匹配的数据结构，核心优势是利用字符串的公共前缀来减少查询时间。

为什么需要Trie？

如果用哈希表存储所有单词，虽然查找单词是O(1)，但要判断"是否存在某个前缀"就很麻烦了。

Trie的关键思想：把字符串拆成字符，一个字符占一层，共享公共前缀。

比如存储 "apple"、"app"、"apply" 三个单词：

        root
         |
         a
         |
         p
         |
         p ← "app"结束
        / \
       l   l
       |   |
       e   y
       |   |
      结束 结束
    "apple" "apply"

可以看到，"app"、"apple"、"apply"共享了"app"这个前缀，节省了存储空间。

Trie的结构

每个节点需要两个关键信息：

1. children：一个数组或哈希表，存储子节点（因为只有小写字母，用大小为26的数组即可）
2. isEnd：布尔值，标记当前节点是否是某个单词的结尾

三个操作的实现

insert(word)：

• 从根节点开始，逐个字符往下走
• 如果路径上的节点不存在，就创建新节点
• 最后一个字符对应的节点，标记 isEnd = true

search(word)：

• 从根节点开始，逐个字符往下走
• 如果中途某个字符找不到对应节点，返回false
• 如果走到最后，检查最后一个节点的 isEnd 是否为true

startsWith(prefix)：

• 和 search 类似，但走到最后不需要检查 isEnd
• 只要路径存在就返回true

模拟过程

以示例中的操作为例：

操作1：insert("apple")

创建路径：root → a → p → p → l → e (isEnd=true)

操作2：search("apple")

查找路径：root → a → p → p → l → e
检查 e.isEnd == true → 返回 true

操作3：search("app")

查找路径：root → a → p → p
检查 p.isEnd == false → 返回 false

操作4：startsWith("app")

查找路径：root → a → p → p
路径存在 → 返回 true

操作5：insert("app")

路径已存在：root → a → p → p
标记 p.isEnd = true

操作6：search("app")

查找路径：root → a → p → p
检查 p.isEnd == true → 返回 true

解题代码

class Trie {
private:
    struct TrieNode {
        TrieNode* children[26]; // 26个小写字母
        bool isEnd; // 当前节点是否是某个单词的结尾
        
        TrieNode() : isEnd(false) {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
        }
    };
    
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new TrieNode(); // 不存在则创建
            }
            node = node->children[index];
        }
        node->isEnd = true; // 标记单词结尾
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false; // 路径不存在
            }
            node = node->children[index];
        }
        return node->isEnd; // 检查是否是完整单词
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (node->children[index] == nullptr) {
                return false; // 路径不存在
            }
            node = node->children[index];
        }
        return true; // 路径存在即可，不需要检查isEnd
    }
};

复杂度分析

• 时间复杂度：插入、查找、前缀查询都是O(L)，L 是字符串长度
• 空间复杂度：O(N × L × 26)，N 是单词数量，L 是平均长度，26 是字符集大小；实际中因为共享前缀，空间会更少

其他语言

Python3

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

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            index = ord(c) - ord('a')
            if not node.children[index]:
                node.children[index] = Trie()
            node = node.children[index]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self
        for c in word:
            index = ord(c) - ord('a')
            if not node.children[index]:
                return False
            node = node.children[index]
        return node.isEnd

    def startsWith(self, prefix: str) -> bool:
        node = self
        for c in prefix:
            index = ord(c) - ord('a')
            if not node.children[index]:
                return False
            node = node.children[index]
        return True

Java

class Trie {
    private class TrieNode {
        TrieNode[] children;
        boolean isEnd;
        
        TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }
    
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }
}

Go

type Trie struct {
    children [26]*Trie
    isEnd    bool
}

func Constructor() Trie {
    return Trie{}
}

func (this *Trie) Insert(word string) {
    node := this
    for _, c := range word {
        index := c - 'a'
        if node.children[index] == nil {
            node.children[index] = &Trie{}
        }
        node = node.children[index]
    }
    node.isEnd = true
}

func (this *Trie) Search(word string) bool {
    node := this
    for _, c := range word {
        index := c - 'a'
        if node.children[index] == nil {
            return false
        }
        node = node.children[index]
    }
    return node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
    node := this
    for _, c := range prefix {
        index := c - 'a'
        if node.children[index] == nil {
            return false
        }
        node = node.children[index]
    }
    return true
}

JavaScript

var Trie = function() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
};

Trie.prototype.insert = function(word) {
    let node = this;
    for (let c of word) {
        const index = c.charCodeAt() - 'a'.charCodeAt();
        if (!node.children[index]) {
            node.children[index] = new Trie();
        }
        node = node.children[index];
    }
    node.isEnd = true;
};

Trie.prototype.search = function(word) {
    let node = this;
    for (let c of word) {
        const index = c.charCodeAt() - 'a'.charCodeAt();
        if (!node.children[index]) {
            return false;
        }
        node = node.children[index];
    }
    return node.isEnd;
};

Trie.prototype.startsWith = function(prefix) {
    let node = this;
    for (let c of prefix) {
        const index = c.charCodeAt() - 'a'.charCodeAt();
        if (!node.children[index]) {
            return false;
        }
        node = node.children[index];
    }
    return true;
};

与代码随想录联系

Trie 是字符串处理中非常重要的数据结构，常用于：

• 自动补全（搜索引擎、输入法）
• 拼写检查
• IP 路由匹配
• 敏感词过滤

在代码随想录中，虽然没有单独的 Trie 章节，但在字符串和设计类题目中会涉及。

如果录友们对树形结构还不够熟悉，建议先系统学习 代码随想录二叉树章节，理解树的递归思想后，再来学习 Trie 会更顺畅。

相关题目还有：

• 79. 单词搜索 — 在二维网格中搜索单词，可以用 Trie 优化多单词搜索
• 139. 单词拆分 — 也可以用 Trie 存储字典