Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Word Search

LeetCode #79Medium
DFS with mark-and-unmark backtracking

Given a grid of characters and a target word, return whether the word can be formed by a path of 4-directionally adjacent cells, where each cell may be used at most once.

Asked atAmazonMicrosoftBloomberg
step 1 / 31
3 × 4 board · word = "ABCCED"
A
B
C
E
S
F
C
S
A
D
E
E
Backtracking · DFS mark & unmark
▸
1exist(word):
2    for each start cell == word[0]:
3        if dfs(r, c, 0): return true
4dfs(r, c, i):                  // board[r][c] == word[i]
5    mark (r, c) used
6    if i == last index: return true
7    for each neighbour (nr, nc):
8        if used or letter != word[i+1]: skip
9        if dfs(nr, nc, i+1): return true
10    unmark (r, c)              // backtrack
11    return false
state
  • wordABCCED
  • len6
  • size3 × 4

line 1Word Search: can we spell "ABCCED" by walking the grid one letter at a time, moving up/down/left/right, never re-using a cell? The plan is DFS with mark-and-unmark backtracking. We try a start cell that matches the first letter, mark it used, then recurse into neighbours that match the next letter. If a branch dead-ends we UN-MARK and try another direction.