Multi-Word Grid & Stream Pruning

Foundations

So far, each search walked the trie for one query at a time. Now, what if letters arrive one by one, along a path through a grid or from a stream, and you need every stored word those letters could spell?

Treat the trie as a state machine. The state is the trie node matching the letters read so far, starting at the root. Each new letter either follows a child edge to the next state or finds no edge, and the path dies right there; a state with isEnd set reports a word. One walk tracks every stored word at once, because words sharing a prefix share their states.

Scan s = "tinn" for the words in words = ["to", "tea", "ten", "inn"], starting a walk at each index. From index 0, t is a state, but t has no child i, so the walk dies after one letter. From 1, i, n, and n follow edges to an isEnd node: inn. Walks from 2 and 3 die at once, since the root has no n.

• Constraint Pruning on Grids & Boards

  That lesson's backtracking marks a step as used, tries its neighbors, and unmarks it on return. This lesson steers the same search with a trie.

  Open lesson

Case Scenario

Word Search II asks for every word from words that can be traced on a letter board by moving between adjacent cells, using each cell at most once per word. Every path through the board is a stream of letters, so one trie of all the words prunes each path the moment it leaves the trie. For words = ["oath", "pea", "eat", "rain"] on the example board, the answer is ["oath", "eat"].

The direct approach runs Word Search once per word: try every cell as a start and backtrack across the board. Words that share a start repeat the same walks, and the work grows with the dictionary: w words cost w full board searches, though one walk could check all of them at once.