Word Search
- 2 min read
- Graph
- Ae-medium
- LC-Medium
- Algoexpert
- Backtracking
3 years ago
Solution
Do a Backtracking Depth-first Search. We use a visited set to keep track of the current path. Whenever we're done with a path, we remove all the elements from the visited set. This is because we don't want our subsequent DFSs to ignore characters we already saw- they might have previously been in an order we didn't want. But that doesn't mean we shouldn't look at them. After each DFS, the visited set is reset to null because of our remove statements. Since we return True immediately, we never see the visited set with one element or more since we immediately exit the program after the return.
| Time | Space | Explanation |
|---|---|---|
O(r * c * 4^n) | O() | You go through each row and column, and do DFS on each cell. n is the number of characters in the word. 4^n because DFS goes in 4 directions |
def exist(self, board: List[List[str]], word: str) -> bool:
nrows, ncols = len(board), len(board[0])
visited = set()
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or r >= nrows or c < 0 or c >= ncols or (r, c) in visited or board[r][c] != word[i]:
return False
visited.add((r, c))
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = r + dr, c + dc
if dfs(nr, nc, i + 1):
return True
visited.remove((r, c))
for r in range(nrows):
for c in range(ncols):
if dfs(r, c, 0):
return True
return False