[Trie] Design Add and Search Words Data Structure

211. Design Add and Search Words Data Structure

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

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

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

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

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

  for (const each of word) {
    if (!cur.children.has(each)) {
      cur.children.set(each, new TrieNode());
    }

    cur = cur.children.get(each);
  }

  cur.isEndOfWord = true;
};

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

    const c = word[0];

    if (c === ".") {
      const ans = [];

      for (const [_, child] of node.children) {        
        ans.push(searchRecursive(child, word.substring(1)));
      }      

      return ans.some((each) => each);
    } 
    
    const child = node.children.get(c);

    if (!child) {
      return false;
    }

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

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

/** 
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */

연관된 직전 게시글에서 [Trie] Implement Trie (Prefix Tree) TrieNode의 children 필드를 JS객체를 사용하였지만, 본 해답에서는 Map을 사용하였습니다. 그 이유는 .와 같이 children을 모두 순회해야하는 경우가 있기 때문입니다.

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

2-1. Using trie more simple

해답의 전문은 링크를 확인해주세요.

...
WordDictionary.prototype.search = function (word) {
  // helper function to call recursively
  const searchHelper = (currentNode, i) => {
    // if we reach the i that's the length of word and currentNode is a word ending, word exists.
    if (i === word.length) return currentNode.isWordEnding;

    const char = word[i];

    // if char is a dot, that means we can match it with any letter.
    // to do that programmatically, we go through all of the children of the current node. why?
    // we don't know which, if any, of the children can use the dot to make the given string.
    // so we go through all of them and check if any of them can return true.
    if (char === ".") {
      for (const char of Object.keys(currentNode.children)) {
        const child = currentNode.children[char];
        if (searchHelper(child, i + 1)) return true;
      }

      // if no child can make use of the dot to come up with the given word,
      // then even the alternative version (e.g 'pad')
      // of the given string (e.g 'pa.') doesn't exist in our dictionary.
      return false;
    }

    // if char isn't a dot, it's more straightforward...
    else {
      // looking for a letter that should come after another and can't find it?
      // that means the word doesn't exist in our dictionary so return false.
      if (!(char in currentNode.children)) return false;

      // go on to the next node in our dictionary and the next letter in the word
      return searchHelper(currentNode.children[char], i + 1);
    }
  };

  // we call this function by starting at our root node with the index for the first letter in the string
  return searchHelper(this.root, 0);
};

children을 순회하면서 유효한 child인지 판별하는 과정을 중점적으로 살펴보았습니다. 필자의 해답은 판별 결과를 배열로 집계한 뒤, some 배열 메소드로 유효한 값만 걸러내었습니다. 본 해답은 판별을 수행하는 재귀함수 결과값이 boolean 타입이기 때문에 이를 유효한 값만 걸러내는 로직에 바로 활용하였습니다.