Why it works
- The walk steps into a cell only when the trie has a child for its letter, so the path so far is always the start of some word. A path that is the start of no word stops at once.
- One walk serves every word at the same time: "ten" and "tea" share "te", which is walked once, and each word is found when the walk reaches the node that holds it.
- The # mark keeps one path from using a cell twice, and the unmark on the way back frees it for other paths. Clearing the word from its node keeps a word that two paths spell from being added twice.
Complexity
Time O(m·n · 4 · 3^(L−1)) in the worst case for an m×n grid and words of up to L letters: a walk starts from each cell, the first step has 4 directions and every later one at most 3. The trie usually cuts this short. Memory O(total letters of the words) for the trie and O(L) for the call stack.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗