高效的字符串前缀匹配

问题

给定一组字符串，如何高效地判断某个前缀是否存在，或者找出所有匹配某前缀的字符串？

解答

为什么用 Trie 树

暴力遍历每个字符串检查前缀，时间复杂度是 O(n * m)，n 是字符串数量，m 是前缀长度。

Trie 树（前缀树）把公共前缀合并存储，查询时间复杂度降到 O(m)，与字符串数量无关。

Trie 树实现

class TrieNode {
  constructor() {
    this.children = {};  // 子节点映射
    this.isEnd = false;  // 是否是某个单词的结尾
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // 插入单词
  insert(word) {
    let node = this.root;
    for (const char of word) {
      // 如果字符不存在，创建新节点
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEnd = true;  // 标记单词结尾
  }

  // 搜索完整单词
  search(word) {
    const node = this._findNode(word);
    return node !== null && node.isEnd;
  }

  // 判断是否存在某前缀
  startsWith(prefix) {
    return this._findNode(prefix) !== null;
  }

  // 找到前缀对应的节点
  _findNode(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) {
        return null;
      }
      node = node.children[char];
    }
    return node;
  }

  // 获取所有匹配前缀的单词
  getWordsWithPrefix(prefix) {
    const results = [];
    const node = this._findNode(prefix);
    
    if (node) {
      this._collectWords(node, prefix, results);
    }
    return results;
  }

  // 递归收集所有单词
  _collectWords(node, currentWord, results) {
    if (node.isEnd) {
      results.push(currentWord);
    }
    for (const [char, childNode] of Object.entries(node.children)) {
      this._collectWords(childNode, currentWord + char, results);
    }
  }
}

使用示例

const trie = new Trie();

// 插入单词
['apple', 'app', 'application', 'banana', 'band'].forEach(word => {
  trie.insert(word);
});

// 搜索完整单词
console.log(trie.search('app'));      // true
console.log(trie.search('ap'));       // false

// 前缀匹配
console.log(trie.startsWith('app'));  // true
console.log(trie.startsWith('ban'));  // true
console.log(trie.startsWith('cat'));  // false

// 获取所有匹配前缀的单词
console.log(trie.getWordsWithPrefix('app'));  // ['app', 'apple', 'application']
console.log(trie.getWordsWithPrefix('ban'));  // ['banana', 'band']

搜索框自动补全场景

class AutoComplete {
  constructor(words) {
    this.trie = new Trie();
    words.forEach(word => this.trie.insert(word.toLowerCase()));
  }

  // 返回最多 limit 个建议
  suggest(prefix, limit = 5) {
    const words = this.trie.getWordsWithPrefix(prefix.toLowerCase());
    return words.slice(0, limit);
  }
}

// 使用
const ac = new AutoComplete(['JavaScript', 'Java', 'Python', 'JSON', 'jQuery']);
console.log(ac.suggest('ja'));  // ['javascript', 'java']
console.log(ac.suggest('j'));   // ['javascript', 'java', 'json', 'jquery']

关键点

• Trie 树把公共前缀合并，节省空间，加速查询
• 查询时间复杂度 O(m)，m 是前缀长度，与数据量无关
• 每个节点用 isEnd 标记是否是完整单词
• 适用场景：搜索建议、自动补全、拼写检查、IP 路由
• 空间换时间，适合前缀查询频繁的场景