[CS] Trie

Trie

ソースコード

class Node {
    constructor(value = "") {
        this.value = value;
        this.children = new Map();
        this.isWord = false;
    }
}
class Trie {
    constructor() {
        this.root = new Node();
    }
    
    insert(string) {
        let currentNode = this.root;
        for(const char of string) {
            if (!currentNode.children.has(char)) {
                currentNode.children.set(
                    char,
                    new Node(currentNode.value + char)
                );
            }
            currentNode = currentNode.children.get(char);
        }
        currentNode.isWord = true;
    }
    has(string) {
        let currentNode = this.root;
        for(const char of string) {
            if(!currentNode.children.has(char)) {
                return false;
            }
            currentNode = currentNode.children.get(char);
        }
        return true;
    }
    autoComplete(string) {
        let wordList = [];
        const stack = [];
        let currentNode = this.root;
        if(!string.length) return wordList;
        
        for(const char of string) {
            if(currentNode.children.has(char)) 
                currentNode = currentNode.children.get(char);
            else 
                return wordList;        
        }

        if (currentNode.isWord) wordList.push(currentNode.value);

        stack.push(currentNode);
        while(stack.length > 0) {
            currentNode = stack.shift();
            if(currentNode.children.size > 0) {
                for (const [_, node] of currentNode.children) {
                    stack.push(node);

                    if (node.isWord)
                      wordList.push(node.value);
                }
            } 
        }

        return wordList;

trie.insert('cow');
trie.insert('coworker');
trie.insert('cookie');
trie.insert('mic');
trie.insert('mickey');
console.log(trie.autoComplete('co')); // ['cow', 'cookie', 'coworker', 'code']
console.log(trie.autoComplete('ca')); // [ 'cat', 'can', 'cap' ]
console.log(trie.autoComplete('mi')); // [ 'mic', 'mickey' ]
console.log(trie.autoComplete('')); // []