This problem follows the Grid DFS + Backtrack pattern, commonly found in the Backtracking category. Recognizing this pattern is key to solving it efficiently in an interview setting.
DFS from each cell. Mark visited. If char matches, recurse to neighbors. Unmark on backtrack.
Modifying the board in-place (then restoring) avoids the overhead of a visited set — this is a classic space optimization for grid backtracking.
def exist(board, word):
def dfs(i, j, k):
if k == len(word): return true
if i<0 or j<0 or i>=rows or j>=cols: return false
if board[i][j] != word[k]: return false
temp = board[i][j]
board[i][j] = '#' # mark visited
found = dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
board[i][j] = temp # backtrack
return found
for i in range(rows):
for j in range(cols):
if dfs(i, j, 0): return true
return falsePractice Word Search and similar Backtracking problems with flashcards. Build pattern recognition through active recall.
Practice this problem