<Demopeu/>

[LeetCode] 208 Implement Trie (Prefix Tree) JavaScript

[LeetCode] 208 Implement Trie (Prefix Tree) JavaScript

problem-solvingLeetCodeTrieHash TableClassMapPrototype

📌 문제 설명

Implement Trie (Prefix Tree) 문제 보기

📌 문제 접근

처음 생각

트라이 자료구조라도 Set()을 사용하면 되는거 아닐까? 하지만, Set()을 사용하면 startWith 메서드에서 모든 노드를 탐색해야 하므로 비효율적일 것 같다. 그래도 search 메서드는 효율적이지 않을까 했지만, 공간활용도를 생각하면 비효율적일 것 같았다. 그래서 내 처음 코드는 Map()을 사용하였다.

const Trie = function() {
    this.map = new Map();
};

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    const len = word.length;
    let value = this.map;
    for (let i = 0;i<len;i++){
        const new_value = value.get(word[i]) || new Map();
        value.set(word[i],new_value);
        value = new_value;
    }
    value.set(`isEnd`,true);
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let value = this.map;
    for (const w of word){
        if (value.has(w)) value = value.get(w);
        else return false;
    }
    return value.has(`isEnd`);
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let value = this.map;
    for (const w of prefix){
        if (value.has(w)) value = value.get(w);
        else return false;
    }
    return true;
};

하지만, isEnd가 Map객체 안에 있어서 상태관리가 불편하게 보여서 자료구조를 하나 만들어서 사용하였다.

📌 내가 작성한 코드

class TrieNode {
    constructor() {
        this.end = false;
        this.children = new Map();   
    }
}


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

/** 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let now = this.root;
    for (let i = 0;i<word.length;i++){
        if (!now.children.has(word[i])) now.children.set(word[i], new TrieNode());
        now = now.children.get(word[i]);
    }
    now.end = true;
};

/** 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let now = this.root;
    for (const w of word){
        if (now.children.has(w)) now = now.children.get(w);
        else return false;
    }
    return now.end;
};

/** 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let now = this.root;
    for (const w of prefix){
        if (now.children.has(w)) now = now.children.get(w);
        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)
 */

📌 시간 복잡도

O(L) - insert/search/startsWith 모두 입력 문자열 길이 L만큼 문자 노드를 따라 이동합니다.

📌 참고 링크