跳到主要内容

字典树

字典树是什么？​

  • 别名: 前缀树 (Trie);
  • 结构: 每个单词表现为从根节点出发的一条路径;
  • 根节点: 不包含字符;
  • 其他节点: 只包含一个字符;
  • 路径含义: 从根节点到某个节点的路径, 拼出该节点对应的字符串;
  • 约束: 同一个节点的子节点字符互不相同;

字典树的节点如何定义？​

  • children: 子节点集合, 常用哈希表存储, 字符为键、子节点为值;
  • isEnd: 标记该节点是否是一个单词的结尾;
class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

如何插入单词并创建字典树？​

  • 插入: 从根节点出发逐字符下行;
    • 对应子节点不存在则新建, 再指向它;
    • 对应子节点存在则直接指向它;
  • 收尾: 单词处理完毕后, 把当前节点的 isEnd 置为 true;
  • 创建: 初始化空字典树, 再逐个插入所有单词;
class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let cur = this.root;
    for (const ch of word) {
      if (!cur.children.has(ch)) cur.children.set(ch, new TrieNode());
      cur = cur.children.get(ch)!;
    }
    cur.isEnd = true;
  }
}

查找单词与查找前缀有什么区别？​

  • 共同路径: 两者都从根节点逐字符下行, 中途缺失子节点即返回 false;
  • 查找单词: 走完全部字符后还要检查 isEnd, 否则只是某个单词的前缀;
  • 查找前缀: 走完全部字符即可返回 true, 不检查 isEnd;
search(word: string): boolean {
  const node = this.traverse(word);
  return node !== null && node.isEnd;
}

startsWith(prefix: string): boolean {
  return this.traverse(prefix) !== null;
}

private traverse(text: string): TrieNode | null {
  let cur = this.root;
  for (const ch of text) {
    if (!cur.children.has(ch)) return null;
    cur = cur.children.get(ch)!;
  }
  return cur;
}