211. Design Add and Search Words Data Structure

문제링크: https://leetcode.com/problems/design-add-and-search-words-data-structure/

단어를 추가하고 단어가 사전에 존재하는지 확인하는 클래스를 만든다. 찾는 단어 중 .은 어느 단어가 들어가도 된다.

Solution

Trie with object

Trie 자료구조를 통해 단어를 저장하고 찾을 수 있다. 대신에 .문자를 만났을 때 이어지는 모든 트리를 탐색해야 된다. 이 부분은 bfs보다는 dfs를 통해 찾는 것이 효율적이기 때문에 dfs재귀를 통해 구현한다.

Algorithm

*TrieNode를 지정한다. TrieNode는 다음 TrieNode로 가는 next Letter 포인터들을 저장한다.

• addWord는 trie 재귀를 통해 단어를 저장한다. ''는 끝을 의미
• search는 기존 trie는 반복을 통해서 탐색만 하면 되지만 '.'이 포함되어 있는 경우는 모든 가능한 단어를 탐색해야된다.
• DFS재귀를 통해 문자를 탐색하고 '.'를 만났을 때는 모든 단어 노드를 탐색한다.
• 단어를 찾고 다음 노드에 ''가 있을 경우 true를 반환한다.

class TrieNode {
  constructor() {
    this.next = {};
  }
  
  addNextLetter(val) {
    this.next[val] = new TrieNode();
    // '' 가 end
  }
}

var WordDictionary = function() {
  // trie를 만드는데 점이 포함되면 아무 letter나 가능하다.
  this.node = new TrieNode();
};

/** 
 * @param {string} word
 * @return {void}
 */
WordDictionary.prototype.addWord = function(word) {
  // Trie를 확인하면서 없으면 새 노드 생성
  let cur = this.node;
  for (let w of word) {
    if (!cur.next[w]) {
      cur.addNextLetter(w);
    }
    cur = cur.next[w];
  }
  // last end
  if (!cur.next['']) {
    cur.addNextLetter('');
  }
};

/** 
 * @param {string} word
 * @return {boolean}
 */
WordDictionary.prototype.search = function(word) {
  // dfs
  const dfs = (cur, wordIdx) => {
    if (wordIdx >= word.length) {
      if (cur.next['']) return true;
      else return false;
    }
    
    if (word[wordIdx] === '.') {
      for (let key of Object.keys(cur.next)) {
        if (dfs(cur.next[key], wordIdx + 1)) return true;
      }
      return false;
    } else {
      if (cur.next[word[wordIdx]]) {
        return dfs(cur.next[word[wordIdx]], wordIdx + 1);
      } else {
        return false;
      }
    }

  }
  return dfs(this.node, 0);
};