使用ES6类javaScript的Trie的实现

Question

每次针对不同的测试用例都会产生相同的答案。在我尝试创建Trie数据结构的代码中，该结构存储和检索字符串的最高优先级以用于后续查询。例如。我想到了创建搜索引擎类型模式。

请帮助我解决我的问题-

输入-

hackerearth 10

黑客5

class TrieNode {
  constructor(priority) {
    this.priority = priority;
    this.children = []
    for (let i = 0; i < 26; i++) {
      this.children.push(null)
    }
  }
}

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

  createNode(priority) {
    let obj = new TrieNode(priority)
    return obj;
  }

  max(a, b) {
    if (a > b) {
      return a;
    }
    return b;
  }

  insertNode(word, priority) {
    let ptr = this.root;
    for (let i = 0; i < word.length; i++) {
      if (ptr.children[word[i] - 'a'] != null) {
        ptr.children[word[i] - 'a'].priority = this.max(ptr.children[word[i] - 'a'].priority, priority)
      } else {
        ptr.children[word[i] - 'a'] = this.createNode(priority)
      }
      ptr = ptr.children[word[i] - 'a']
    }
  }
  checkNode(word) {
    let ptr = this.root;
    for (let i = 0; i < word.length; i++) {
      if (ptr.children[word[i] - 'a'] === null) {
        return -1;
      }
      ptr = ptr.children[word[i] - 'a']
    }
    return ptr.priority;
  }

}

let a = new Trie();
a.insertNode("hackerearth", 10);
a.insertNode("hackerman", 5);
console.log(a.root.children['h' - 'a'])
console.log(a.checkNode("hackerf"))

结果始终相同：

TrieNode {
  priority: 10,
  children: [
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    NaN: TrieNode { priority: 10, children: [Array] }
  ]
}
10

Answer 1

您不能只减去字符串。您需要将它们转换为字符代码。

class TrieNode {
  constructor(priority) {
    this.priority = priority;
    this.children = [] // I would not initialize
  }
}

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

  createNode(priority) {
    let obj = new TrieNode(priority)
    return obj;
  }

  max(a, b) {
    if (a > b) {
      return a;
    }
    return b;
  }

  insertNode(word, priority) {
    let ptr = this.root;
    const a = "a".charCodeAt(0); // store value of a
    for (let i = 0; i < word.length; i++) {
      const index = word[i].charCodeAt(0) - a // calculate difference
      if (ptr.children[index] != null) {
        ptr.children[index].priority = this.max(ptr.children[index].priority, priority)
      } else {
        ptr.children[index] = this.createNode(priority)
      }
      ptr = ptr.children[index]
    }
  }
  checkNode(word) {
    let ptr = this.root;
    const a = "a".charCodeAt(0);
    for (let i = 0; i < word.length; i++) {
      // just check for false
      if (!ptr.children[word[i].charCodeAt(0) - a]) {
        return -1;
      }
      ptr = ptr.children[word[i].charCodeAt(0) - a]
    }

    return ptr.priority;
  }

}

let a = new Trie();
a.insertNode("hackerearth", 10);
a.insertNode("hackerman", 5);
console.log(a.checkNode("hacker"))
console.log(a.checkNode("hackee"))
console.log(a.checkNode("hackerm"))
console.log(a.checkNode("hackerf"))