📚 단일 패턴

208. Implement Trie (Prefix Tree)

문자 단위로 노드를 확장해 삽입·검색·접두어 검사를 지원하는 Trie 자료구조 구축 방법 정리

Oct 22, 2025

문제 설명

LeetCode 208. Implement Trie (Prefix Tree) (opens in a new window)

풀이 아이디어

텍스트 순서 비교 시 Trie 를 사용하면 빠르게 비교 가능.
apple, app 으로 구성한 trie 구조
워드의 끝은 node["word"] 로 확인.

{
   "a":{
      "p":{
         "p":{
            "l":{
               "e":{
                  "word":"apple"
               }
            },
            "word":"app"
         }
      }
   }
}

해결 전략

Trie

구현

var Trie = function() {
    this.trie = {};
};

/**
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let node = this.trie;
    for (const ch of word){
        if (node[ch] === undefined) node[ch] = {};
        node = node[ch];
    }
    node["word"] = word;
};

/**
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let node = this.trie;
    for (const ch of word) {
        if (node[ch] === undefined) return false;
        node = node[ch];
    }
    return !!node["word"];
};

/**
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let node = this.trie;
    for (const ch of prefix) {
        if (node[ch] === undefined) return false;
        node = node[ch];
    }
    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)
 */