The problem
Write a trie class (lessons 1 and 2). insert(word) stores a word. search(word) returns True if the word was inserted. starts_with(prefix) returns True if at least one inserted word starts with the prefix.
t = Trie()
t.insert("apple")
t.search("apple") # True
t.search("app") # False: only a prefix
t.starts_with("app") # True
t.insert("app")
t.search("app") # True
Words and prefixes are non-empty and use the letters a to z. The same word may be inserted more than once.
Limits
- Up to 30,000 words and 60,000 searches, each word at most 7 letters. Every operation should take O(L) time for a word of length L, whatever the number of stored words.
Builds on TRIE-1 Prefix trees and TRIE-2 Insert, search and delete.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
8 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Word and prefix | Not run | |
| 2 | Shared paths | Not run | |
| 3 | Empty trie | Not run | |
| 4 | Longer than any word | Not run | |
| 5 | Inserted twice | Not run | |
| 6 | Word inside a word | Not run | |
| 7 | One letter words | Not run | |
| 8 | 30,000 words | Not run |