9. 字典树（Trie / 前缀树）

问题：需要按前缀快速查找字符串，如搜索自动补全、拼写检查、IP 路由。

核心：每个节点代表一个字符，从根到某节点的路径对应一个字符串前缀。查找只与字符串长度 m 有关，与总数据量无关。

特点

每条边代表一个字符，根到节点路径 = 字符串
查找/插入时间 O(m)，m 为字符串长度
节点可标记是否为单词结尾

优点

前缀查找极快，O(m) 与数据量无关
天然支持前缀匹配、自动补全
无哈希冲突问题

缺点

空间开销大，每个字符一个节点
只适合字符串场景
大量公共前缀少时效率不如哈希表

class TrieNode {
  children = {};
  isEnd = false;
}

class Trie {
  #root = new TrieNode();

  insert(word) {
    let node = this.#root;
    for (const ch of word) {
      node.children[ch] ??= new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  search(word) {
    const node = this.#walk(word);
    return node?.isEnd ?? false;
  }

  startsWith(prefix) {
    return this.#walk(prefix) !== null;
  }

  #walk(str) {
    let node = this.#root;
    for (const ch of str) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }

  // 自动补全：返回所有以 prefix 开头的词
  autocomplete(prefix) {
    const node = this.#walk(prefix);
    if (!node) return [];
    const results = [];
    const dfs = (n, path) => {
      if (n.isEnd) results.push(prefix + path);
      for (const [ch, child] of Object.entries(n.children)) {
        dfs(child, path + ch);
      }
    };
    dfs(node, '');
    return results;
  }
}

const trie = new Trie();
['apple', 'app', 'application', 'banana'].forEach(w => trie.insert(w));

console.log(trie.search('app'));              // true
console.log(trie.search('ap'));               // false
console.log(trie.startsWith('ap'));           // true
console.log(trie.autocomplete('app'));        // ['app', 'apple', 'application']

package trie

type TrieNode struct {
    Children map[rune]*TrieNode
    IsEnd    bool
}

func newTrieNode() *TrieNode {
    return &TrieNode{Children: make(map[rune]*TrieNode)}
}

type Trie struct {
    root *TrieNode
}

func NewTrie() *Trie {
    return &Trie{root: newTrieNode()}
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if _, ok := node.Children[ch]; !ok {
            node.Children[ch] = newTrieNode()
        }
        node = node.Children[ch]
    }
    node.IsEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.walk(word)
    return node != nil && node.IsEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.walk(prefix) != nil
}

func (t *Trie) walk(s string) *TrieNode {
    node := t.root
    for _, ch := range s {
        child, ok := node.Children[ch]
        if !ok {
            return nil
        }
        node = child
    }
    return node
}

搜索引擎自动补全、拼写检查、IP 路由表（路由前缀匹配）、IDE 代码补全都使用字典树加速前缀查找。