题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

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

说明:

  • 你可以假设所有的输入都是由小写字母 a-z 构成的。

  • 保证所有输入均为非空字符串。

来源：LeetCode

思路

维护一棵树，子节点为一个长度为 26 的数组。每一个字母存在对应位置上。节点还要有一个字段标记其是否是叶子节点，叶子节点表示至此是一个完整单词。

解法

const aCode = 97;

class TreeNode {
  constructor(value = '') {
    this.value = value;
    this.children = [];
    this.leaf = false;
  }
}

class Trie {
  constructor() {
    this.tree = new TreeNode();
  }

  insert(word) {
    let node = this.tree;

    for (let char of word) {
      const code = char.charCodeAt();
      const index = code - aCode;

      if (!node.children[index]) {
        node.children[index] = new TreeNode(char);
      }
      node = node.children[index];
    }

    node.leaf = true;
  }

  search(word) {
    let node = this.tree;

    for (let char of word) {
      const code = char.charCodeAt();
      const index = code - aCode;

      if (!node.children[index]) return false;

      node = node.children[index];
    }

    return node.leaf;
  }

  startsWith(prefix) {
    let node = this.tree;

    for (let char of prefix) {
      const code = char.charCodeAt();
      const index = code - aCode;

      if (!node.children[index]) return false;

      node = node.children[index];
    }

    return true;
  }
}