```
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
row = len(board)
col = len(board[0])
visited = [[False] * col for i in range(row)]
for i in range(row):
for j in range(col):
if board[i][j] == word[0]:
result = self.dfs(board, visited, i, j, row, col, word[1:])
if result:
return True
return False
def dfs(self, board, visited, i, j, row, col, word):
if word == '':
return True
visited[i][j] = True
for m, n in [(i, j + 1), (i, j - 1), (i - 1, j), (i + 1, j)]:
if 0 <= m and m <= row - 1 and 0 <= n and n <= col - 1 and board[m][n] == word[0] and not visited[m][n]:
if self.dfs(board, visited, m, n, row, col, word[1:]):
return True
visited[i][j] = False
return False
```