LeetCode 208. Implement Trie (Prefix Tree) JavaScript로 풀기 — 트라이 자료구조 쉽게 이해하기

구려...

---

✅ 문제 설명
문제 이름: Implement Trie (Prefix Tree)
링크: LeetCode 208

✅ 문제 요구사항

• Trie라는 자료구조를 구현하세요.
  - insert(word): 문자열 word를 트라이에 삽입
  - search(word): word가 정확히 존재하는지 반환 (true / false)
  - startsWith(prefix): prefix로 시작하는 단어가 하나라도 존재하는지 반환

---

트라이(Trie)란?

트라이는 문자열을 빠르게 저장하고 검색하기 위한 트리형 자료구조다.
단어를 문자 하나씩 잘라서 노드로 연결하고, 같은 접두사(prefix)를 공유하는 구조로 되어 있다.

주로 자동완성 기능 (ex: 검색창), 단어 사전 구현, 접두사 기반 검색, 문자열 집합에서 빠르게 찾기에 쓰인다.

예시 1: apple을 저장하면

root
 └─ a
     └─ p
         └─ p
             └─ l
                 └─ e (여기에 isEnd = true)

단어가 끝나는 마지막 글자에는 isEnd = true 표시를 붙여 "여기서 하나의 단어가 끝난다"는 걸 표시한다.

예시 2: apple, app, apt를 저장하면

root
 └─ a
     ├─ p
     │   ├─ p (끝 표시)
     │   │   └─ l
     │   │       └─ e (끝 표시)
     └─ p
         └─ t (끝 표시)

---

JavaScript 코드로 구현하기

기본 구조

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

root는 트리의 시작점이다. 각 노드는 {} 형태의 객체이며, 알파벳을 키로 사용한다.

insert(word): 단어 삽입

Trie.prototype.insert = function(word) {
    let node = this.root;
    for (let letter of word) {
        if (node[letter] === undefined) node[letter] = {};
        node = node[letter];
    }
    node.isEnd = true; 
};

여기서 node는 지금 현재 글자를 삽입할 위치를 가리키는 포인터다. 매 글자마다 트리를 따라 내려가며, 없으면 새로 만들어주고 다음 글자로 이동한다.

insert("apple")의 수행 흐름

• 시작: node = root = {}
• "a"가 없으니까 node["a"] = {} 만들고 이동
• "p"가 없으니까 node["p"] = {} 만들고 이동
• 반복해서 "l" → "e"까지
• 마지막 "e" 위치에 isEnd = true 표시

이 과정을 마치고 나면 root는 이렇게 된다.

{
  a: {
    p: {
      p: {
        l: {
          e: {
            isEnd: true
          }
        }
      }
    }
  }
}

search(word): 단어 존재 여부 확인

Trie.prototype.search = function(word) {
    let node = this.root;
    for (let letter of word) {
        if (!node[letter]) return false;
        node = node[letter];
    }
    return node && node.isEnd === true;
};

"a" → "p" → "p" → "l" → "e" 한 글자씩 따라간다.
중간에 끊기면 false, 끝까지 가더라도 isEnd가 true여야 진짜 단어로 인정한다.

startsWith(prefix): 접두사 확인

Trie.prototype.startsWith = function(prefix) {
    let node = this.root;
    for (let letter of prefix) {
        if (!node[letter]) return false;
        node = node[letter];
    }
    return true;
};

isEnd는 체크하지 않는다. 단어가 완성되지 않아도, 경로만 존재하면 true이다.

---

전체 코드

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

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

    for(let letter of word) {
        if (node[letter] === undefined) node[letter] = {};
        node = node[letter];
    }

    node.isEnd = true;
};

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

    for(let letter of word) {
        if(!node[letter]) return false;
        node = node[letter];
    }

    return node && node.isEnd === true;
};

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

    for(let letter of prefix) {
        if(!node[letter]) {
            return false;
        } else {
            node = node[letter];
        }
    }

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