Why it works
- A word is stored as a path of letters from the root, so every word that starts with the same letters walks through the same nodes, and find reaches the node for any prefix in as many steps as the prefix has letters.
- Reaching the node only proves that some word starts this way. A whole word needs its own end mark: that is the one difference between search and startsWith.
- A word that is the start of a longer one, like "to" in "top", already has its path. Inserting it adds no node and only sets the mark.
Complexity
Time O(L) per call, where L is the length of its word: one step per letter. Memory O(total letters of the inserted words): at most one node per letter, fewer when words share a start.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗