Idea is to do DFS on every position of the board, return True as soon as their is a valid path.

Use visited as a set to store the positions that have been visited, preventing going back to visited positions. Need to undo the visited at the end.

```
def exist(self, board, word):
for i in range(len(board)):
for j in range(len(board[0])):
if self.dfs(board, word, i, j, 0, set()):
return True
return False
def dfs(self, board, word, i, j, index, visited):
if index >= len(word): return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or (i, j) in visited or board[i][j] != word[index]: return False
visited.add((i, j))
ret = self.dfs(board, word, i+1, j, index+1, visited) or self.dfs(board, word, i-1, j, index+1, visited) or self.dfs(board, word, i, j-1, index+1, visited) or self.dfs(board, word, i, j+1, index+1, visited)
visited.remove((i, j))
return ret
```