Coding Interview Patterns Module 19 – Tries
Many words in a grid: trie plus DFS
Find every word of a long list on a board of letter tiles with one depth-first walk per tile through a trie, then cut off finished branches.
What you will learn
- Find every listed word on a letter board with one depth-first walk per tile through a trie
- Explain why each word is reported once and why no tile is used twice in a word
- Measure what cutting off finished branches saves on 12 × 12 boards
- Estimate the cost of the walk and compare it with one grid search per word
- Extend the walk to eight neighbours, counting paths and reusing the trie on many boards
Before you start
What you’ll learn · Before you start
What you will learn
- Find every listed word on a letter board with one depth-first walk per tile through a trie
- Explain why each word is reported once and why no tile is used twice in a word
- Measure what cutting off finished branches saves on 12 × 12 boards
- Estimate the cost of the walk and compare it with one grid search per word
- Extend the walk to eight neighbours, counting paths and reusing the trie on many boards
Before you start
On this page
To find many words in a grid with a trie plus DFS, run one depth-first walk from each tile of the board, and let it follow the board and a trie of all the words at the same time. The walk steps onto a neighbouring tile only when the trie has a child for that tile’s letter, marks the tile while it is on the path and frees it on the way back, and reports a word whenever it reaches a node where one ends. So one walk from each tile checks every word at once, where the brute force runs a separate grid search for each word. Interviews know the problem as word search II: a board of letters, a long list of words, and the question of which words the board holds.
The problem: city names on a board
The problem
A city quiz shows a board of letter tiles and a list of city names. A name counts when the board spells it along a
chain of tiles in which each tile lies above, below, left or right of the one before, and no tile appears twice.
Write words_on_board(board, words), which returns the names that can be spelled, in alphabetical order, each
once. The board has 1 to 12 rows and columns of lowercase letters; the list has up to 10,000 names of 1 to 12
letters, and may repeat a name.
On the board below, the list agra, erode, goa, kochi, kota, patna, pune, puri, ranchi, salem and pune again gives seven names: agra, goa, kochi, kota, patna, pune and puri. erode, ranchi and salem are not on the board.
Two names that start with ko share one branch of the trie
Text description of the diagram
The top half is the board of the worked problem, five rows of five letter tiles: e p a t n, then n u r i a, then k o c h m, then a a o t a, then g r k g o.
- The name kochi is drawn as a solid line over shaded tiles. It starts at the k on the left edge of the middle row, runs right through o, c and h along that row, and then goes up to the i above the h.
- The name kota is drawn as a dashed line over tiles with dashed borders. It starts at the k in the middle of the bottom row, goes up to the o above it, then right through t to the a at the right edge of the fourth row.
The bottom half is the part of the trie below k. The nodes k and ko come first, in one row. From ko the row goes on through koc and koch to kochi, which has a double border because a name ends there. A dashed line leaves ko downwards to a second row, kot and then kota, which also has a double border.
So a walk that starts on either k tile follows the same two trie nodes, k and ko, and only then needs a c or a t next to the o it has reached.
The brute force, and why it fails at these sizes
Run the single-word search of the grid backtracking lesson once for every name in the list, from every tile, and keep the names it finds:
"""The brute force for the city quiz: one grid search for every word of the list."""
BOARD = ["epatn", "nuria", "kochm", "aaota", "grkgo"]
CITIES = ["agra", "erode", "goa", "kochi", "kota", "patna", "pune", "puri", "ranchi", "salem", "pune"]
def word_in_board(board, word, counter):
"""Can word be spelled along neighbouring tiles, each tile at most once? counter[0] counts tiles stepped on."""
rows, cols = len(board), len(board[0])
taken = [[False] * cols for _ in range(rows)]
def spell(r, c, i):
counter[0] += 1
if board[r][c] != word[i]:
return False
if i == len(word) - 1:
return True
taken[r][c] = True
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < rows and 0 <= nc < cols and not taken[nr][nc] and spell(nr, nc, i + 1):
taken[r][c] = False
return True
taken[r][c] = False
return False
return any(spell(r, c, 0) for r in range(rows) for c in range(cols))
def words_on_board_brute(board, words):
counter = [0]
found = sorted({w for w in words if word_in_board(board, w, counter)})
return found, counter[0]
if __name__ == "__main__":
for row in BOARD:
print(" " + " ".join(row))
found, steps = words_on_board_brute(BOARD, CITIES)
print(f"{len(CITIES)} names in the list, {len(set(CITIES))} different; found {len(found)}: {', '.join(found)}")
print(f"{steps} tiles stepped on: one search for each name in the list")
words, starts, length = 10_000, 12 * 12, 10
per_start = 4 * 3 ** (length - 2) # four first moves, then three at most from every later tile
print()
print(f"At the limits: {words:,} words × {starts} starting tiles × {per_start:,} paths of {length} tiles")
print(f"= {words * starts * per_start:,} steps in the worst case")Output
e p a t n n u r i a k o c h m a a o t a g r k g o 11 names in the list, 10 different; found 7: agra, goa, kochi, kota, patna, pune, puri 233 tiles stepped on: one search for each name in the list At the limits: 10,000 words × 144 starting tiles × 26,244 paths of 10 tiles = 37,791,360,000 steps in the worst case
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 brute.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
On the example it steps on 233 tiles. In the worst case, a search of a 10-letter word can try 4 × 3⁸ = 26,244 paths from each of the 144 tiles of a 12 × 12 board, so 10,000 words make up to 3.8 × 10¹⁰ steps. Compiled code manages around 10⁸ simple steps a second, the planning figure of the constraints lesson, so that is several minutes of work.
What to notice
The names share their starts: pune, puri and patna begin with p, and kochi and kota with ko. Separate searches walk those shared starts again for every name, on the same tiles. A trie stores each start once, so a walk that follows the trie tests every name with that start in one go, and it stops at the first tile whose letter continues no name at all.
Walking the board and the trie together Pro: opens with a Pro, Premium or Ultimate pass
In this part:
- Why every name is found, once
- A dry run from one k tile
- The code in five languages
- Cutting off finished branches, measured on 12 × 12 boards
- What the walk costs, with numbers
- Edge cases and common bugs
- Variants: eight neighbours, counting paths, many boards
- Exercise
- Every city name on a board of letter tiles
- A practice set with sample answers
- Check yourself
- Interview questions
- A 12 × 12 board and 10,000 words: estimate how much work one walk per tile through a trie saves over a separate grid search for every word, and describe a list of words for which it saves almost nothing.
- Your words_on_board passes small tests but runs for minutes on a 12 × 12 board of a's with the words a, aa and so on up to twelve a's. Explain where the time goes, estimate it, and fix it without changing any answer.
- The rules change: a tile may be used more than once in a word, but never twice in a row. What changes in the walk, why does it still end, and what does it cost on a 12 × 12 board with words of up to 10 letters?
- A quiz server checks one list of 50,000 words against a new 5 × 5 board every second, for thousands of rooms at once. Design the search so each board is fast, explain how the trie is shared between boards and rooms, and estimate memory and time per board.
- Key takeaways
5 runnable examples (Build and run all three, C++, Go, Java, JavaScript, Python) · 1 exercise with sample tests · 4 interview answers · about 29 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
References
- trie (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology)
- depth-first search (Dictionary of Algorithms and Data Structures) (National Institute of Standards and Technology)
- sys.setrecursionlimit (The Python Standard Library) (Python Software Foundation)
- time.perf_counter (The Python Standard Library) (Python Software Foundation)
- Mapping types: dict (The Python Standard Library) (Python Software Foundation)
- ECMAScript language specification: Map.prototype.delete (Ecma International (TC39))
- String.toCharArray (Java SE 25 API specification) (Oracle)
- std::size, std::ssize (cppreference.com) (cppreference.com)
- Package slices: Sort (The Go Authors)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress