Trie树

发布时间:2019-05-05 22:00:18发布者:Mr.Zhang阅读(236)

class TrieNode {
    constructor(data){
        this.data = data
        this.children = new Array(26)
        this.isEndingChar = false
        this.text = ''
    }
}

class TrieTree {
    constructor(){
        this.root = new TrieNode('/')
    }
    insert(text){
        let currentNode = this.root
        for(let char of text){
            let index = char.charCodeAt() - 'a'.charCodeAt()
            if(!currentNode.children[index]){
                currentNode.children[index] = new TrieNode(char)
            }
            currentNode = currentNode.children[index] 
        }
        currentNode.isEndingChar = true
        currentNode.text = text
    }
    find(text){
        let currentNode = this.root
        for(let char of text){
            let index = char.charCodeAt() - 'a'.charCodeAt()
            if(currentNode.children[index]){
                currentNode = currentNode.children[index]
            } else {
               return {
                input:text,
                result: false
               }
            }
        }
        return {
            input:currentNode.text,
            result:currentNode.isEndingChar
        }
    }
}

let tree = new TrieTree()
let strs = ["how", "hi", "her", "hello", "so", "see"];
for(let str of strs) {
    tree.insert(str);
}

for(let str of strs) {
    console.log(tree.find(str));
}

console.log(tree.find('world'));




本文转自博客园,原文地址:https://www.cnblogs.com/pluslius/p/10813557.html