Loading page…
Practice problem · medium
A search box suggests words while you type. Behind it sits an index that stores words and answers two questions: is this exact word stored, and does any stored word start with these letters.
You build that index. It receives a list of commands, one at a time, each with a word.
Write run_trie(commands, words).
commands[i] is "insert", "search" or "starts_with", and words[i] is its word.insert stores the word. Its answer is the number of new nodes the index had to make for it. Storing a word that is already there makes 0.search answers 1 when exactly this word was inserted, and 0 when it was not. A word that is only the start of a stored word gives 0.starts_with answers 1 when some inserted word starts with these letters, and 0 when none does.Input: commands = ["insert", "insert", "search", "search", "starts_with", "starts_with"], words = ["car", "cat", "car", "ca", "ca", "dog"]
Output: [3, 1, 1, 0, 1, 0]| Command | Word | What happens | Answer |\n|---|---|---|---|\n| insert | car | 3 new nodes: c, a, r | 3 |\n| insert | cat | c and a exist, 1 new node: t | 1 |\n| search | car | the walk ends on a word end | 1 |\n| search | ca | the walk works, but no word ends there | 0 |\n| starts_with | ca | the walk works | 1 |\n| starts_with | dog | there is no edge d | 0 |
Input: commands = ["insert", "insert"], words = ["go", "go"]
Output: [2, 0]The second go finds every node already there and makes none.
Input: commands = ["search"], words = ["x"]
Output: [0]Nothing is stored yet, so there is no edge x.
1 ≤ length of commands ≤ 5000, and commands and words have the same lengthinsert, search or starts_witha to z)There can be 5,000 commands with words of 20 letters. Keeping the words in a list and scanning it for each command costs thousands of comparisons each time.
A trie answers a command by walking the letters of its word, whatever the number of stored words.
run_trie · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.