Why does this trie search return true for prefixes that were never inserted as full words?

programming web dev
1

I’m implementing a small trie in TypeScript. Exact word lookup should only return true for inserted words, but prefixes like “car” become searchable after inserting “cart”. I think my traversal is fine, so I’m probably marking nodes incorrectly. What is the minimal fix here?

class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}
function insert(root: TrieNode, word: string) {
  let node = root;
  for (const ch of word) {
    if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
    node = node.children.get(ch)!;
    node.isWord = true;
  }
}

WaffleFries

2

You’re marking every traversed node as a word, so car gets flagged while inserting cart.

Quelly :grinning_face: