Word Search
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
Does a word exist in a grid of letters, spelled by moving up, down, left or right, using each cell at most once?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Try every cell as the starting tile; which neighbours can come next?
- Hint 2How do you stop reusing the same cell on one path, yet allow it on another path?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A letter puzzle on the floor tiles. To spell the word, stand on a tile with the first letter, chalk a cross on it so you do not step there again, and step to a neighbouring tile with the second letter, and so on. If you get stuck you walk back and rub off the chalk on the tile you leave, so another route may use it.
- The obvious way
Try all paths from every cell: this is the idea, pruned by the first letter check.
- The key insight
For each cell start a depth-first search that has matched 0 letters. At a cell: if all letters matched, True. If outside the grid or the letter differs, False. Otherwise chalk it (temporarily replace the letter), try the four neighbours for the next letter, then restore the letter and report whether any worked.
- The algorithm
- For every cell, search with matched = 0.
- All letters matched: True. Outside or wrong letter: False.
- Chalk the cell, try 4 neighbours with matched + 1.
- Rub the chalk off, return the result.
Watch it run
Exampleword = "ABCCED" on grid A B C E / S F C S / A D E E
Start on the first A (top-left), then its right neighbour B, then C: the first three letters ABC are matched.
matched: A B C
Where people slip
- Restore the cell after the search; forgetting it corrupts other attempts.
- Check matched == len first, otherwise the last letter's neighbours are out of bounds.
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 exist(board, word):
rows, columns = len(board), len(board[0])
def walk(row, column, matched):
if matched == len(word):
return True # every letter found
if row < 0 or row >= rows or column < 0 or column >= columns:
return False
if board[row][column] != word[matched]:
return False
letter = board[row][column]
board[row][column] = "#" # chalk: do not step here again
found = (walk(row + 1, column, matched + 1) or walk(row - 1, column, matched + 1) or
walk(row, column + 1, matched + 1) or walk(row, column - 1, matched + 1))
board[row][column] = letter # rub the chalk off
return found
for row in range(rows):
for column in range(columns):
if walk(row, column, 0):
return True
return FalseNow 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.