Vấn đề
Chúng ta cần triển khai một lớp MapSum với các phương thức insert và sum. Với phương thức insert, chúng ta sẽ nhận một cặp (chuỗi, số nguyên). Chuỗi đại diện cho khóa và số nguyên đại diện cho giá trị. Nếu khóa đã tồn tại, cặp khóa-giá trị gốc sẽ bị ghi đè bằng cặp mới.
Với phương thức sum, chúng ta sẽ nhận một chuỗi đại diện cho tiền tố, và cần trả về tổng giá trị của tất cả các cặp có khóa bắt đầu bằng tiền tố đó.
Ví dụ
Dưới đây là mã:
class Node { constructor(val) { this.num = 0; this.val = val; this.children = {}; } } class MapSum { constructor(){ this.root = new Node(''); } } MapSum.prototype.insert = function (key, val) { let node = this.root; for (const char of key) { if (!node.children[char]) { node.children[char] = new Node(char); } node = node.children[char]; } node.num = val; }; MapSum.prototype.sum = function (prefix) { let sum = 0; let node = this.root; for (const char of prefix) { if (!node.children[char]) { return 0; } node = node.children[char]; } const helper = (node) => { sum += node.num; const { children } = node; Object.keys(children).forEach((key) => { helper(children[key]); }); }; helper(node); return sum; }; const m = new MapSum(); console.log(m.insert('apple', 3)); console.log(m.sum('ap'));Đầu ra
undefined 3