MediumNeetCode150ArrayBacktrackingMatrix
Word Search
Check if word exists in grid.
Examples
Input
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output
true
Path exists.
Constraints
- •
m,n <= 6, word <= 15 - •
board/word lowercase English
Approaches
Try DFS from every start.
CodeT: O(m*n*4^L) | S: O(L) recursion depth
def exist(board, word):
r=len(board); c=len(board[0])
def dfs(i,j,k):
if k==len(word): return True
if i<0 or i>=r or j<0 or j>=c or board[i][j]!=word[k]: return False
tmp=board[i][j]; board[i][j]='#'
res=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]=tmp
return res
for i in range(r):
for j in range(c):
if dfs(i,j,0): return True
return FalseEarly termination.
CodeT: O(m*n*4^L) | S: O(L)
Same approach.
CodeT: O(m*n*4^L) | S: O(L)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| DFS from Each Cell | O(m*n*4^L) | O(L) recursion depth | Try DFS from every start. |
| DFS Pruned | O(m*n*4^L) | O(L) | Early termination. |
| DFS Optimization | O(m*n*4^L) | O(L) | Same approach. |
DFS from Each Cell
T: O(m*n*4^L)S: O(L) recursion depth
Try DFS from every start.
DFS Pruned
T: O(m*n*4^L)S: O(L)
Early termination.
DFS Optimization
T: O(m*n*4^L)S: O(L)
Same approach.
Common Mistakes
Not restoring board state
Exploring all 4 dirs when unnecessary
Not checking word length vs board size