Trie (префиксное дерево)

1class Trie {
2  private root: Node = { char: '·', children: new Map<string, Node>(), end: false }
3 
4  insert(word: string): void {
5    let node = this.root
6    for (const ch of word) {
7      let next = node.children.get(ch)
8      if (next === undefined) {
9        next = { char: ch, children: new Map(), end: false }
10        node.children.set(ch, next)
11      }
12      node = next
13    }
14    node.end = true
15  }
16 
17  has(word: string): boolean {
18    let node = this.root
19    for (const ch of word) {
20      const next = node.children.get(ch)
21      if (next === undefined) return false
22      node = next
23    }
24    return node.end
25  }
26}
27 
28interface Node {
29  char: string
30  children: Map<string, Node>
31  end: boolean
32}