Implement Trie (Prefix Tree)
Implement a trie with insert(word), search(word) and startsWith(prefix). (In the playground, each line is one operation.)
A way to picture it
Think of a phone's autocomplete as a tree of letters. Typing “c-a” walks two steps down from the root, and every word below that spot starts with “ca”. A ★ on a node means a whole word ends right there.
How to approach it
Each node maps a letter to a child and has an end-of-word flag. Words sharing a prefix share the path. search needs the flag; startsWith doesn't.
Example
Input: {"ops":["insert apple","search apple","search app","startsWith app","insert app","search app"]}. Output: [null,true,false,true,null,true].
Complexity: O(L) per operation time and O(total letters) space. L is the word length; each letter is one step.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.