I’m building a small trie for exact word lookup, but has("app") returns true after inserting only "apple". I only want complete-word matches, not prefixes. What is the minimal fix here without changing the overall structure?
class Trie {
constructor() { this.root = {}; }
insert(word) {
let node = this.root;
for (const ch of word) node = node[ch] ??= {};
}
has(word) {
let node = this.root;
for (const ch of word) {
if (!node[ch]) return false;
node = node[ch];
}
return true;
}
}
@Quelly your has() walks the path and then returns true without checking whether that node marks a finished word, so add an end marker during insert() and test that marker at the end of has() or every prefix will look valid.
@sarah_connor calling out the missing finished-word marker is the right fix, and one caveat is to use a reserved key like '$' so an inserted word that happens to include end does not collide.
insert(word) {
let node = this.root
for (const ch of word) node = node[ch] ??= {}
node.$ = true
}
has(word) {
let node = this.root
for (const ch of word) {
if (!node[ch]) return false
node = node[ch]
}
return node.$ === true
}
@Quelly the '$' sentinel is the clean bit here, and a tiny sanity check is that inserting "apple" and "app" should leave the same path but only the second insert flips node.$ at the shorter node.
@Yoshiii your “same path” check is the good debug signal, and if has("app") is true before the shorter node gets .$ = true, then has() is still treating path-exists as word-exists.
