[leetcode]208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/implement-trie-prefix-tree/submissions/1717889324/
트라이 클래스를 구현해보는 문제이다.
트라이에 대한 설명은 알고달레에서 참고했다.
https://www.algodale.com/data-structures/trie/

Trie() Initializes the trie object.

void insert(String word) Inserts the string word into the trie.

boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

boolean startsWith(String prefix) Returns true if there is a previously
inserted string word that has the prefix prefix, and false otherwise.

---

1. class 기반 Trie

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

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEnd = true;
    }

    search(word) {
        const node = this._traverse(word);
        return node !== null && node.isEnd;
    }

    startsWith(prefix) {
        return this._traverse(prefix) !== null;
    }

    _traverse(str) {
        let node = this.root;
        for (let char of str) {
            if (!node.children[char]) return null;
            node = node.children[char];
        }
        return node;
    }
}

---

2. function + prototype 기반 Trie

function TrieNode() {
    this.children = {};
    this.isEnd = false;
}

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

Trie.prototype.insert = function(word) {
    let node = this.root;
    for (let char of word) {
        if (!node.children[char]) {
            node.children[char] = new TrieNode();
        }
        node = node.children[char];
    }
    node.isEnd = true;
};

Trie.prototype.search = function(word) {
    const node = this._traverse(word);
    return node !== null && node.isEnd;
};

Trie.prototype.startsWith = function(prefix) {
    return this._traverse(prefix) !== null;
};

Trie.prototype._traverse = function(str) {
    let node = this.root;
    for (let char of str) {
        if (!node.children[char]) return null;
        node = node.children[char];
    }
    return node;
};

---

시간 복잡도

메서드	시간 복잡도	설명
insert	O(L)	L = 단어 길이
search	O(L)	L = 단어 길이
startsWith	O(L)	L = 접두사 길이

---

공간 복잡도

• 최악의 경우: O(N × L)

  • N: 삽입된 단어 개수
  • L: 평균 단어 길이

• 중복된 접두사가 많으면 훨씬 줄어듦 (공유 구조 덕분)

---

class vs prototype 방식 차이 정리

항목	class 방식	function + prototype 방식
문법 도입	ES6 (2015년)	ES5 이하
가독성	높음	낮음
new 없이 호출	❌ 오류 발생	✅ 가능
strict mode	기본 적용됨	수동 적용 필요
상속	extends, super로 간단	복잡한 수작업 필요
호이스팅	❌ 안 됨	✅ 가능
실질 동작	둘 다 prototype 기반	동일

---