[JS] 접두사 트라이

1. 노드

class TrieNode {
  children = new Map();
  endOfWord = 0;
}

2. 추가하기

class Trie {
  root = new TrieNode();

  insert(word) {
    let cur = this.root;

    for (let i = 0, l = word.length; i < l; i += 1) {
      const char = word[i];
      
      if (!cur.children.has(char)) cur.children.set(char, new TrieNode());
      cur = cur.children.get(char);
    }

    cur.endOfWord += 1;
  }
}

3. 탐색

class Trie {
  root = new TrieNode();

  insert(word) {
    // ...
  }

  search(word) {
    let cur = this.root;

    for (let i = 0, l = word.length; i < l; i += 1) {
      const char = word[i];
      
      if (!cur.children.has(char)) return false;
      cur = cur.children.get(char);
    }

    return cur.endOfWord > 0;
  }
}

4. 삭제

class Trie {
  root = new TrieNode();

  insert(word) {
    // ...
  }

  search(word) {
    // ...
  }

  delete(word, cur = this.root, index = 0) {
    if (index === word.length) {
      if (cur.endOfWord > 0) cur.endOfWord -= 1;
      return cur.endOfWord === 0;
    }

    const char = word[index];
    if (!cur.children.has(char)) return false;

    const node = cur.children.get(char);
    const res = this.delete(word, node, index + 1);
    if (res) cur.children.delete(char);

    return cur.children.size === 0;
  }
}