Why it works
- A plain letter has at most one child to go to, so the walk stays on one path, as in a normal trie search.
- A dot can be any letter, so every child is a possible path. match tries them one by one and only gives up on the dot when all of them returned false, so no stored word that fits is missed.
- At the end of the pattern the node must carry the end mark: reaching it only proves that some stored word starts this way.
Complexity
addWord: time O(L) for a word of L letters, memory O(L) at most for its new nodes. search: time O(L) without dots; each dot can branch to up to 26 children, so a pattern with d dots costs up to O(26^d · L). Memory O(L) for the call stack.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗