A trie that steers another search

The problem, and the obvious approach

You have a grid of letters and a list of words, and you must report which words can be traced through adjacent cells without reusing a cell.

You solved the single-word version in Unit 10. The obvious extension is to run that search once per word, which is correct and costs the full grid search multiplied by the number of words. With a large dictionary that is far too slow.

The search is Unit 10's grid backtracking with one extra parameter and one extra guard. The guard is worth seeing on its own, because it is where all the saving comes from.

Below, no search runs at all. Every cell of a small board is simply asked whether any word in the dictionary could begin there.

1board = [["o", "a"],2         ["e", "t"]]3words = ["oat", "oa", "ate", "zzz"]4 5first_letters = {word[0] for word in words}      # the root's children6 7for row in range(len(board)):8    for col in range(len(board[0])):9        letter = board[row][col]10        verdict = "worth starting" if letter in first_letters else "nothing begins here"11        print(f"({row}, {col}) holds {letter!r}: {verdict}")

Two techniques, one problem

This problem is the reason Tries follows Backtracking rather than sitting elsewhere in the course. Neither technique alone solves it: the backtracking explores the grid and the trie decides which explorations are worth doing.

Before starting, write down the grid search you already know, then add the trie node as a parameter and the child lookup as the first guard. Framed that way it is a modification rather than a new problem.