One effective method to solve this problem is to use Depth-First Search (DFS) combined with backtracking. This approach involves starting from each cell and attempting to find the word by traversing adjacent cells, backtracking whenever a dead end is encountered.
DFS coupled with backtracking will be able to explore each possible path in the grid, returning true if a path spelling out the word is found, and false if all paths have been exhausted without success.
The function should mark a cell as visited before exploring further down its path and should unmark it (backtrack) when returning.
Time Complexity: O(N * 3^L) where N is the number of cells and L is the length of the word. Each cell can have at most 3 valid directions to explore (excluding the direction we came from).
Space Complexity: O(L) due to recursion stack where L is the length of the word being searched.
1class Solution:
2 def exist(self, board: List[List[str]], word: str) -> bool:
3 def dfs(i, j, pos):
4 if pos == len(word): return True
5 if i < 0 or i >= len(board) or j < 0 or j >= len(board[i]) or board[i][j] != word[pos]:
6 return False
7
8 tmp = board[i][j]
9 board[i][j] = '#'
10
11 found = (dfs(i + 1, j, pos + 1) or dfs(i - 1, j, pos + 1) or
12 dfs(i, j + 1, pos + 1) or dfs(i, j - 1, pos + 1))
13
14 board[i][j] = tmp
15 return found
16
17 for i in range(len(board)):
18 for j in range(len(board[i])):
19 if dfs(i, j, 0):
20 return True
21 return FalseThe Python solution employs a nested dfs function for recursive exploration. The cell is temporarily marked with '#' during path exploration and restored after.
An alternative but less optimal approach involves using Breadth-First Search (BFS). This approach can be useful for understanding the search pattern but is generally slower and less ideal compared to DFS for specific pathfinding problems.
Although BFS will attempt to explore each possibility layer-by-layer, it is less effective due to its nature of handling adjacency and backtracking in this specific kind of grid traversal problem. Still, it provides a clearer structure for paths explored and can be integrated with queue data structures for parallel processing.
The key difficulty with BFS in this problem is efficiently pruning unfruitful search branches early, which DFS inherently handles through natural backtracking.
Time Complexity: Generally more than O(N * 3^L) as BFS does not effectively prune unpromising paths dynamically during search.
Space Complexity: O(N) because it may expand and hold large numbers of nodes in the worst case.
1from collections import deque
2
3class Solution:
4 def exist(self, board: List[List[str]], word: str) -> bool:
5 rows, cols = len(board), len(board[0])
6 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
7
8 def is_valid(x, y, index):
9 return 0 <= x < rows and 0 <= y < cols and board[x][y] == word[index]
10
11 for i in range(rows):
12 for j in range(cols):
13 if board[i][j] == word[0]:
14 queue = deque([(i, j, 0)])
15 visited = set()
16 while queue:
17 x, y, index = queue.popleft()
18 if index == len(word) - 1:
19 return True
20 for dx, dy in directions:
21 new_x, new_y = x + dx, y + dy
22 if is_valid(new_x, new_y, index + 1) and (new_x, new_y) not in visited:
23 queue.append((new_x, new_y, index + 1))
24 visited.add((new_x, new_y))
25 return FalseThis Python example uses a deque to handle BFS traversal. For each starting point matching the beginning of word, it attempts to queue possible paths that match subsequent characters. Although this implementation correctly attempts breadth-level searches, it lacks efficiency and effectiveness compared to DFS in terms of space and early pruning.