[LeetCode] Implement Trie (Prefix Tree) - Javascript

Implement Trie (Prefix Tree)

[Trie 자료구조]

제약 조건 

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

Example

ex1) Input
     ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
     [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
     Output
     [null, null, true, false, true, null, true

	Explanation
	Trie trie = new Trie();
	trie.insert("apple");
	trie.search("apple");   // return True
	trie.search("app");     // return False
	trie.startsWith("app"); // return True
	trie.insert("app");
	trie.search("app");     // return True

문제 접근 방식

트라이 자료구조는 문자열을 저장하고 탐색하기 위한 트리모양의 자료구조이다.

보통 문자열 탐색에 많이 사용된다.

 

다만, 문자마다 노드를 만들기에 저장공간이 많이 사용된다.

트라이 자료구조를 이용해 insert, search, startsWith를 구현해야한다.

구현할때 아래와 같은 특성을 고려해 풀이를 해야한다.

 

주어지는 예시를 봤을 때, trie.insert를 통해 'apple' 문자열을 삽입하고,
'apple' 문자열을 trie.search 했을 때 true가 리턴되며 'app'을 search 했을 땐 false가 리턴돼야 한다.
또 'app'문자열을 trie.startWith 했을 땐 true를 리턴하면 된다.

 

각각의 메서드 기능들은 아래와 같은 개념을 생각하며 구현했다.

 

insert

반복문을 사용해 각 노드를 탐색하면서, 

현재 노드가 존재하지는 지 확인하고 존재한다면 이어서 탐색을 하고, 존재하지 않으면 새로운 노드를 생성한다.

탐색이 끝난 후 마지막에 있는 노드의 curr.isWord의 값을 true로 만들어 현재 문자열의 끝 지점이라는 것을 알려준다.

 

search

반복문을 사용해 각 노드를 탐색하면서,

현재 트라이에 해당 문자가 있는지 탐색한다.

만약 해당 문자가 존재하는 경우 계속 이어서 탐색하고 존재하지 않는다면 false를 리턴한다.

반복문이 종료될 때 해당 문자가 마지막인지 알려주는 isWord를 리턴해 true를 리턴한다.

 

startWith 

반복문을 사용해 각 노드를 탐색하면서, 

현재 트라이에 해당 문자가 있는지 탐색한다. 

만약 해당 문자가 존재하는 경우 계속 이어서 탐색하고 존재하지 않는다면 false를 리턴한다. 

반복문이 종료될 때 false가 리턴되지 않았다면 해당 문자열이 존재한다는 의미이기에 true를 리턴한다.(search 방법과 리턴 형식만 다름.)

solve 전체 코드

class TrieNode {
   constructor() {
      this.children = {};
      this.isWord = false;
   }
}

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

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
   let curr = this.root;
   for (let c of word) {
      if (curr.children[c] == null) {
         curr.children[c] = new TrieNode();
      }
      curr = curr.children[c];
   }

   curr.isWord = true;
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
   let curr = this.root;
   for (let c of word) {
      if (curr.children[c] != null) {
         curr = curr.children[c];
      } else {
         return false;
      }
   }

   return curr.isWord;
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
   let curr = this.root;
   for (let c of prefix) {
      if (curr.children[c] != null) {
         curr = curr.children[c];
      } else {
         return false;
      }
   }

   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)
 */