[Trie] Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree)

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

function TrieNode() {
  this.children = {};
  this.isEndOfWord = false;
}

var Trie = function () {
  this.root = new TrieNode();
};

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  let cur = this.root;

  for (const each of word) {
    if (!cur.children[each]) {
      cur.children[each] = new TrieNode();
    }

    cur = cur.children[each];
  }

  cur.isEndOfWord = true;
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  let cur = this.root;  

  for (const each of word) {
    const child = cur.children[each];

    if (!child) {
      return false;
    }
    
    cur = child;
  }    

  return cur.isEndOfWord;
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  let cur = this.root;

  for (const each of prefix) {
    const child = cur.children[each];    

    if (!child) {
      return false;
    }

    cur = child;
  }

  return true;
};

/** 
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

삽입 메소드는 본 프로그램 강의에서 설명된 반복 방법을 참고하였습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

본 프로그램 강의에서 설명된 재귀 방법을 참고하였습니다.

function TrieNode() {
  this.children = {};
  this.isEndOfWord = false;
}

var Trie = function () {
  this.root = new TrieNode();
};

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  const insertRecursive = (node, word) => {
    if(word.length === 0) {
      node.isEndOfWord = true;
      return;
    }

    const c = word[0];    

    if(!node.children[c]) {
      node.children[c] = new TrieNode();
    }

    insertRecursive(node.children[c], word.substring(1));
  }

  insertRecursive(this.root, word);
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  const searchRecursive = (node, word) => {
    if(word.length === 0) {
      return node.isEndOfWord;
    }

    const c = word[0];
    const child = node.children[c];

    if(!child) {
      return false;
    }

    return searchRecursive(child, word.substring(1));
  };

  return searchRecursive(this.root, word);
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  const searchRecursive = (node, word) => {
    if(word.length === 0) {
      return true;
    }

    const c = word[0];
    const child = node.children[c];

    if(!child) {
      return false;
    }

    return searchRecursive(child, word.substring(1));
  };

  return searchRecursive(this.root, prefix);
};