트라이

class Node {
  constructor(value = '') {
    this.value = value;
    this.children = new Map();
    this.count = 0;
  }
}

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

  insert(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new Node(currentNode.value + char));
      }

      currentNode = currentNode.children.get(char);
      currentNode.count += 1;
    }
  }

  has(string) {
    let currentNode = this.root;

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        return false;
      }

      currentNode = currentNode.children.get(char);
    }

    return true;
  }

  getCount(string) {
    let currentNode = this.root;
    let totalCount = 0;

    for (const char of string) {
      totalCount += 1;
      currentNode = currentNode.children.get(char);
      if (currentNode.count === 1) {
        return totalCount;
      }

    }

    return totalCount;
  }
}

=> 자동완성 구현하기 좋은 자료구조형, 단 루트에 자식의 정보를 모두 담아야 하기 때문에 저장공간이 많이 필요하다.