Problem
Given a 2D grid of characters (board) and a word (word), determine if the word can be formed by walking adjacent cells (up/down/left/right).
Constraints:
- Each cell can be used at most once in the path.
Example:
board = [
['B', 'C', 'F', 'E'],
['E', 'A', 'B', 'L'],
['B', 'C', 'D', 'O'],
['E', 'B', 'M', 'O'],
['R', 'G', 'D', 'E'],
]
word = "BLOOMBERG" -> true
word = "BOB" -> false
word = "BEABLE" -> true
Approach
Classic DFS + backtracking:
- Try each cell as a start if it matches the first letter.
- DFS in 4 directions.
- Mark visited during recursion and unmark during backtracking.
Python
def exist(board: list[list[str]], word: str) -> bool:
if not board or not board[0]:
return False
R, C = len(board), len(board[0])
def dfs(r: int, c: int, i: int) -> bool:
if i == len(word):
return True
if r < 0 or r >= R or c < 0 or c >= C:
return False
if board[r][c] != word[i]:
return False
ch = board[r][c]
board[r][c] = '#'
found = (
dfs(r + 1, c, i + 1) or
dfs(r - 1, c, i + 1) or
dfs(r, c + 1, i + 1) or
dfs(r, c - 1, i + 1)
)
board[r][c] = ch
return found
for r in range(R):
for c in range(C):
if board[r][c] == word[0] and dfs(r, c, 0):
return True
return False
Complexity
- Time:
O(R*C*4^L)in worst case - Space:
O(L)recursion depth
Need interview help? Contact OA VO Service
- 📧 Email: [email protected]
- 📱 Phone: +86 17863968105
Need real interview questions? Contact WeChat: Coding0201 to get the questions.