[LeetCode] 208. Implement Trie (Prefix Tree), Medium

1. 문제

• 문제 요구사항에 맞는 트라이를 구현하라.

2. 해결

class TrieNode {
    children:Map<string, TrieNode>;
    isEnd: boolean
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}

class Trie {
    root:TrieNode;

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

    insert(word: string): void {
        let node = this.root;
        
        for(const char of word) {
            if(!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }

        node.isEnd = true;
    }

    search(word: string): boolean {
        let node = this.root;
        
        for(const char of word) {
            if(!node.children.has(char)) return false;
            node = node.children.get(char);
        }
        
        return node.isEnd;
    }

    startsWith(prefix: string): boolean {
        let node = this.root;
        
        for(const char of prefix) {
            if(!node.children.has(char)) return false;
            node = node.children.get(char);
        }
        
        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)
 */

• 트라이에 대해서 처음 들어봤다.
• 보통 문자열을 검색할 때 효율적으로 사용할 수 있다고 한다.