Why it works
- Every product that starts with a prefix passes through that prefix's node when it is inserted, so the node sees all of its candidates.
- The products are inserted in sorted order, so the first 3 that pass through a node are the 3 smallest, and the node can stop taking words once it has 3.
- Typing walks one node per letter. Once a letter is missing, no product starts with the typed letters, and none starts with any longer prefix either, so every later list is [].
Complexity
Time O(n log n · L) to sort n products of up to L letters, plus O(total letters) to insert them and O(len(searchWord)) to type: each list is ready in its node. Memory O(total letters): a node per letter with at most 3 words in it.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗