advanced

Review: the prefix that answers as a word

This is recall. The code looks finished and is wrong. Find the defect and fix it. You are graded on tests you cannot see.

The deduplication service indexes banned identifiers in a trie and answers "is this identifier banned?" with a walk. Exact matches work. Absent identifiers correctly answer no.

interface TrieNode {
  children: Map<string, TrieNode>
  isEndOfWord: boolean
}

/**
 * Indexes `words` and answers whether an exact query is one of them.
 */
export class WordIndex {
  #root: TrieNode = { children: new Map(), isEndOfWord: false }

  insert(word: string): void {
    let node = this.#root
    for (const ch of word) {
      let next = node.children.get(ch)
      if (next === undefined) {
        next = { children: new Map(), isEndOfWord: false }
        node.children.set(ch, next)
      }
      node = next
    }
    node.isEndOfWord = true
  }

  contains(query: string): boolean {
    let node: TrieNode | undefined = this.#root
    for (const ch of query) {
      node = node.children.get(ch)
      if (node === undefined) return false
    }
    return node !== undefined
  }
}

review — find the defectCtrl+↵ submits · Ctrl+Shift+↵ runsstarter code