Word Search II
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given a grid of letters and a list of words, return all words that can be formed by walking through adjacent cells (each cell once per word).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What would you do for a single word? How does a trie let you handle many words at once?
- Hint 2Stop exploring a path when the trie has no child for the next letter.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A board-game where you must find any of many hidden words. Instead of reading the word list over and over, you build a tree of the first letters, second letters, and so on. Then you walk across the board with a finger, and the tree tells you at every step whether any word could still be spelled by continuing. If the tree has no such continuation you stop walking immediately.
- The obvious way
Run Word Search once per word: O(words x cells x 4^length).
- The key insight
Build a trie of the words (store the whole word on the node where it ends). From every cell start a DFS holding the current trie node: the cell's letter must be a child; if that child holds a word, record it (and remove the word so it is reported once); chalk the cell, visit the neighbours, un-chalk. Pruning: when a node has no children left, delete it from its parent.
- The algorithm
- Build the trie from all words.
- From each cell, DFS following trie children.
- Child holds a word: add it to the answer, clear it.
- Chalk, visit 4 neighbours, un-chalk; prune empty trie nodes.
Watch it run
Exampleboard rows: o a a n / e t a e / i h k r / i f l v; words = oath, pea, eat, rain
From the top-left o: the trie has o -> a -> t -> h. The board lets us walk o, a, t, h: "oath" found.
found: oath
Where people slip
- Remove a found word from the trie (or mark it) so duplicates are not reported twice.
- Un-chalk the cell after exploring, or other words lose their path.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def find_words(board, words):
root = {}
for word in words:
node = root
for letter in word:
node = node.setdefault(letter, {})
node["$"] = word # a whole word ends here
rows, columns = len(board), len(board[0])
found = []
def explore(row, column, parent):
letter = board[row][column]
node = parent.get(letter)
if node is None:
return # no word continues this way
if "$" in node:
found.append(node.pop("$")) # report each word once
board[row][column] = "#" # chalk
for next_row, next_column in ((row + 1, column), (row - 1, column), (row, column + 1), (row, column - 1)):
if 0 <= next_row < rows and 0 <= next_column < columns and board[next_row][next_column] != "#":
explore(next_row, next_column, node)
board[row][column] = letter # rub the chalk off
if not node:
parent.pop(letter) # prune a branch with nothing left
for row in range(rows):
for column in range(columns):
explore(row, column, root)
return foundNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.