Topic 13 of 15
Trie
A tree of letters.
A trie is a tree where each branch is a letter. Words that start the same way share the start of the path, like cat and car sharing c, a. Walking down the letters of a word tells you right away if it, or anything starting with it, is in the tree.
What you will be able to do
Insert and searchPrefix queriesCounting words with a prefixAutocompleteWord break with a trie
0/6
Meet the trie
01 / 04
An empty trie is just a root.
- looking now
- answer
- path
- just added
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Construct a trie from scratchBuild a letter tree where words that start the same way share the same branches, so looking up a word or a start only walks its letters.Trie
- 02Find shortest unique prefix for every word in a given listGive every word the shortest start that no other word shares, by counting how many words walk through each letter of a trie.Trie
- 03Word Break Problem (Trie solution)Decide whether a string with no spaces can be cut into dictionary words, by walking a trie of the dictionary from every spot where a word could start.Trie
- 04Given a sequence of words, print all anagrams togetherPut words made of the same letters into the same group, by sorting each word into a key and filing the keys in a trie.Trie
- 05Implement a Phone DirectoryAs someone types a name letter by letter, show every contact that starts with what they typed so far.Trie
- 06Print unique rows in a given boolean matrixPrint each different row of a grid of 0s and 1s once, by threading every row through a trie that only has a 0 branch and a 1 branch.Trie