Word Search With a Trie
Tries: lesson 3 of 4
One walk over the grid, pruned the moment the path stops being a prefix.
Lesson 3 of 4 · 6 min
Word Search With a Trie
Step 1 of 8
Two words sit in a trie: car and cat. Every cell is a possible first letter.
The Idea
Searching a grid for one word is a depth-first walk. Searching for fifty words that way is fifty walks.
Put the word list in a trie and the walk carries a trie node with it. Every step checks one thing: is this letter a child? If not, no word can grow here and the entire branch dies — that pruning is the whole win.
Real-World Example
A word-game app validating a player's board sweep. It has one dictionary and hundreds of possible paths; chasing each path until the letters stop being a real prefix is what keeps the hint button instant.
The Code
grid = [["c", "a", "r"], ["x", "t", "y"]]
trie = {"c": {"a": {"r": {"$": 1}, "t": {"$": 1}}}}
found = set()
def dfs(r, c, node, word):
ch = grid[r][c]
if ch not in node: return # dead prefix — prune this branch
node, word = node[ch], word + ch
if "$" in node: found.add(word)
grid[r][c] = "#" # no cell twice inside one word
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
if 0 <= r + dr < 2 and 0 <= c + dc < 3:
dfs(r + dr, c + dc, node, word)
grid[r][c] = ch # put it back for other paths
for r, c in [(r, c) for r in range(2) for c in range(3)]: dfs(r, c, trie, "")
print(sorted(found))Your turn
Put the steps in the right order.
- Mark the cell blocked and recurse into the four neighbours
- Read the letter in the current cell
- Unblock the cell so a later path may use it
- Stop unless that letter is a child of the current trie node
- Record the word if this trie node carries the end-of-word flag
Mini quiz
1 / 3