Word Search

Medium#79path on a grid

You get a board of letters and a word. Say whether the word can be read along a path of cells, each next cell touching the one before it up, down, left or right, with no cell used twice. Our example: the board TE / OT / TO and the word TOTE → true.

79 Word SearchWalkthrough · 1×

Example: the board TE / OT / TO (rows top to bottom) and TOTE. Watch (0, 0) when the path asks it for the second T: it holds T, but it is marked #, because the path started there.

01012TEOTTOword0T1O2T3E
free cellon the path, marked #this call's cell, letter matchesturned away: wrong letter or #dead end, letter put backthe path found

Can TOTE be read along a path of touching cells, each cell used once?

01/41
restart · back · play · step
Speed
1function exist(board, word):
2 for each cell of board:
3 if found(cell, 0):
4 return true
5 return false
6
7function found(cell, k):
8 if board[cell] != word[k]: return false
9 if k == len(word) - 1: return true
10 board[cell] = '#' // in use: no second visit
11 ok = any(found(n, k + 1) for n in around(cell))
12 board[cell] = word[k] // free it for other paths
13 return ok
state
cell
–
k
–
n
–
ok
–
click a step to go back

← → step · space play/pause

Why it works

  1. A call answers one question: can word[k:] be read starting at this cell? Its own letter must match, and then one neighbour must answer yes for word[k + 1:], so a true at the top means a real path.
  2. While a cell is on the path it holds #, which matches no letter, so a call that comes back to it turns itself away: no cell is read twice.
  3. Every call puts its letter back before it returns, so a dead end leaves the board as it found it and the cell is free for other paths.

Complexity

Time O(m × n × 3ᴸ), where L is the length of the word: each of the m × n cells may start a path, and after the first step each cell has at most 3 neighbours that are not the one it came from. Memory O(L): the call stack is at most L deep, and the marks live on the board itself.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.