# Word Search
https://leetcode.com/problems/word-search/
- Mark the current cell as travelled before continuing.
- Use [[backtracking]].
```python
def exist(self, board, word):
self.ROWS = len(board)
self.COLS = len(board[0])
self.board = board
for row in range(self.ROWS):
for col in range(self.COLS):
if self.backtrack(row, col, word):
return True
# no match found after all exploration
return False
def backtrack(self, row, col, suffix):
# bottom case: we find match for each letter in the word
if not suffix:
return True
# Check the current status, before jumping into backtracking
if not (
0 <= row < self.ROWS and
0 <= col < self.COLS and
self.board[row][col] == suffix[0]
):
return False
ret = False
# mark the choice before exploring further.
self.board[row][col] = "#"
# explore the 4 neighbor directions
for rowOffset, colOffset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
ret = self.backtrack(row + rowOffset, col + colOffset, suffix[1:])
# break instead of return directly to do some cleanup afterwards
if ret:
break
# revert the change, a clean slate and no side-effect
self.board[row][col] = suffix[0]
# Tried all directions, and did not find any match
return ret
```