Trie树/字典树

type TrieMap = {
  [key: string]: any;
} & { isEnd?: boolean };

class Trie {
  private map: TrieMap;

  constructor() {
    this.map = {};
  }

  insert(word: string): void {
    let map = this.map;
    // 不断向下深入
    for (let w of word) {
      if (map[w] === undefined) {
        map[w] = {};
      }
      map = map[w];
    }
    map.isEnd = true;
  }

  search(word: string): boolean {
    let map = this.map;
    for (let w of word) {
      if (map[w] === undefined) return false;
      map = map[w];
    }
    return map.isEnd === true;
  }

  startsWith(prefix: string): boolean {
    let map = this.map;
    for (let w of prefix) {
      if (map[w] === undefined) return false;
      map = map[w];
    }
    return true;
  }
}