trie.ts

export default class Trie {
  private tree: any = {};

  public add(s: string): void {
    let cur = this.tree;
    for (const c of s) {
      if (!cur[c]) cur[c] = { isString: false };
      cur = cur[c];
    }
    cur.isString = true;
  }

  public search(s: string): boolean {
    let cur = this.tree;
    for (const c of s) {
      if (!cur[c]) return false;
      cur = cur[c];
    }
    return cur.isString;
  }

  public searchWithPrefix(prefix: string): string[] {
    let cur = this.tree;
    for (const c of prefix) {
      if (!cur[c]) return [];
      cur = cur[c];
    }
    const found: string[] = [];
    const queue: [any, string][] = [];
    queue.push([cur, prefix]);
    while (0 < queue.length) {
      const [v, s] = queue.shift();
      if (v.isString) found.push(s);
      for (const c of Object.keys(v)) {
        if (c === 'isString') continue;
        queue.push([v[c], s + c]);
      }
    }
    return found;
  }

  public dump(): void {
    console.log(JSON.stringify(this.tree, null, 2));
  }
}