Word Search
Determine whether a word can be traced through adjacent grid cells (no diagonals, no cell reused). Try each starting cell; at each matched letter, backtrack into unused neighbours looking for the next letter.
- Category
- Backtracking
- Time complexity
- O(R·C·4^L)
- Space complexity
- O(L)
Pseudocode
try every cell as a start if cell matches word[i], mark used recurse into 4 neighbours for word[i+1] mismatch or dead end ⇒ unmark, backtrack
Reference implementation
def dfs(r, c, i):
if board[r][c] != word[i]: return False
if i == len(word)-1: return True
visited[r][c] = True
found = any(dfs(r+dr,c+dc,i+1) for dr,dc in DIRS)
visited[r][c] = False; return found