Trees and recursion 0/36

Lesson 5 of 5

Tries

Store each shared prefix once, mark where words end, and answer prefix questions by walking one path.

5,758 words · 26 min read

Part 1 of 10 Tries

Tries

A search box that completes a word as we type it keeps a list of words and has to answer one kind of question over and over: which of the words begin with the letters typed so far. A prefix of a word is a run of letters at its start, so m, ma and map itself are prefixes of map. A trie is a tree that stores a set of words in such a way that finding whether any stored word begins with a prefix takes one step for each letter of the prefix, however many words are stored. The first problem asks us to build one.

Write a class Trie that stores words made of lowercase letters. insert(word) adds a word. search(word) returns whether exactly this word has been inserted. startsWith(prefix) returns whether some inserted word begins with prefix.

The input lists the calls in order. The output lists what each call returns, with null for the constructor and for insert.

Constraints

  • Words and prefixes have 1 to 2000 lowercase letters
  • At most 3×1043 \times 10^4 calls in total

Sample · Input

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output

[null, null, true, false, true, null, true]

In the sample, apple is inserted first. search("app") is then false, because app itself was never inserted, and startsWith("app") is true, because apple begins with app. Once app has been inserted too, search("app") is true.

The simplest way to store the words is a list. insert appends the word, and each of the two questions compares its argument with every word in the list. The problem allows 30,000 calls. Suppose the first 15,000 insert a word each and the other 15,000 ask a question:

15,000×15,000=225,000,000 comparisons of two strings15{,}000 \times 15{,}000 = 225{,}000{,}000 \text{ comparisons of two strings}

Even if every comparison stopped at its first letter, this would be slow in Python: a loop of 225 million startswith calls that each failed at the first letter took about 6 seconds when we ran it. A comparison reads letters until the two strings differ, and for long words that begin alike that can be close to 2,000 letters, the longest word the problem allows.

A hash set handles search: it finds a word in time proportional to the word's length, however many words it holds. It does not help with startsWith: the set can say whether app is one of its entries, but it has no way to find the longer entries that begin with app. A second set that held every prefix of every inserted word would make startsWith one lookup as well, but a word of 2,000 letters has 2,000 prefixes, and stored as strings of their own they take 1+2+⋯+2,000=2,001,0001 + 2 + \dots + 2{,}000 = 2{,}001{,}000 letters.

A trie holds the same prefixes, but it stores each one as a single letter added to a shorter prefix.