本文共 1978 字，大约阅读时间需要 6 分钟。

Trie（发音类似 “try”）是一种树形数据结构，常用于高效存储和检索字符串集合中的键。其主要应用场景包括自动补全和拼写检查。Trie通过分叉树的方式组织数据，使得查找和插入操作效率极高。

Trie Class 实现

class Trie {    private class Node {        private boolean isWord; // 标记是否为单词结尾        private HashMap
   
     next; // 子节点映射        public Node(boolean isWord) {            this.isWord = isWord;            this.next = new HashMap<>();        }        public Node() {            this(false);        }    }    private Node root; // 根节点    private int size; // 预留字段，不使用    public Trie() {        this.root = new Node();        size = 0;    }    // 插入单词    public void insert(String word) {        Node current = root;        for (int i = 0; i < word.length(); i++) {            char c = word.charAt(i);            if (!current.next.containsKey(c)) {                current.next.put(c, new Node());            }            current = current.next.get(c);        }        if (!current.isWord) {            current.isWord = true;            size++;        }    }    // 检查单词存在    public boolean search(String word) {        Node current = root;        for (int i = 0; i < word.length(); i++) {            char c = word.charAt(i);            if (!current.next.containsKey(c)) {                return false;            }            current = current.next.get(c);        }        return current.isWord;    }    // 检查是否以某个前缀开头    public boolean startsWith(String prefix) {        Node current = root;        for (int i = 0; i < prefix.length(); i++) {            char c = prefix.charAt(i);            if (!current.next.containsKey(c)) {                return false;            }            current = current.next.get(c);        }        return true;    }}
   

使用示例

Trie trie = new Trie();trie.insert("apple"); // 插入单词bool result = trie.search("apple"); // 检查是否存在单词result = trie.search("app"); // 检查是否存在单词bool startsResult = trie.startsWith("app"); // 检查是否以特定前缀开头

提示

• 单词和前缀的长度不超过2000个字符
• insert、search 和 startsWith 调用次数总计不超过 3 × 104 次
• 单词仅由小写字母组成
• 提高Trie性能的重要因素是复杂度为 O(m)，其中 m 是处理的字符数

转载地址：http://tmhiz.baihongyu.com/