Lesson 05 · Counting distinct words - Build an Autocomplete Engine

Counting distinct words

The engine should know how many distinct words it holds, and that count must not double-count a word inserted twice. Today you make Len exact by only counting a word the first time its end marker flips on.

The goal

Track the number of distinct stored words, counting each word exactly once.

Start here - the target

TO DO

Scenario: Len counts distinct words, ignoring duplicates

Givena new trie

WhenInsert("car"), Insert("cart"), Insert("care") are called

ThenLen() is 3

Anda further Insert("car") leaves Len() at 3, while Insert("cab") raises it to 4

Background

The word count lives on the Trie as size, but the trick is updating it correctly. Marking end unconditionally would let a repeated Insert("car") inflate the count even though no new word arrived. So guard it: only when the final node’s end was false before this insert has a genuinely new word been added, and only then do you flip end and increment size.

Inserting car, cart, care adds three distinct words, so Len() is 3. Inserting car a fourth time finds an already-ended node and changes nothing; inserting cab ends a new node and takes the count to 4. This exact-count guarantee is what lets later lessons trust that “return everything” really means every stored word, once each.

Make it work

func (t *Trie) Insert(word string) {
  cur := t.root
  for _, r := range word {
    // ... walk/create children as before ...
  }
  if !cur.end { // only a NEWLY ended word bumps the count
    cur.end = true
    t.size++
  }
}

CheckpointDONE

Len reports the number of distinct stored words and never double-counts. Commit and stop here.