javascript - 使用 ES6 类 javaScript 实现 Trie

Question

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

请帮我解决我的问题-

输入 -

黑客地球 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

标签： javascriptclassoopdata-structurestrie

Answer 1

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

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("hackere"))
console.log(a.checkNode("hackerm"))
console.log(a.checkNode("hackerf"))

你也可以只使用一个对象而不是一个数组，只使用字符作为属性键。

class TrieNode {
  constructor(priority) {
    this.priority = priority;
    this.children = {}
  }
}

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++) {
      const index = word[i]
      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;
    for (let i = 0; i < word.length; i++) {
      // just check for false
      if (!ptr.children[word[i]]) {
        return -1;
      }
      ptr = ptr.children[word[i]]
    }

    return ptr.priority;
  }

}

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