The tell: Find many words in a grid — searching each one separately is far too slow.
How you get there
1Build a trie of all the words so one grid walk tests every candidate at once.
2DFS the grid, descending the trie in lockstep and pruning when no child matches.
3Mark cells visited during the path and restore them on the way out.
Solution
Python
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
root = TrieNode()
for word in words:
node = root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_word = True
rows, cols = len(board), len(board[0])
found: set[str] = set()
def dfs(r: int, c: int, node, path: str) -> None:
if not (0 <= r < rows and 0 <= c < cols):
return
ch = board[r][c]
child = node.children.get(ch)
if child is None:
return # prune: no word continues this way
path += ch
if child.is_word:
found.add(path)
board[r][c] = "#" # mark visited
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
dfs(r + dr, c + dc, child, path)
board[r][c] = ch # restore
for r in range(rows):
for c in range(cols):
dfs(r, c, root, "")
return list(found)
Time
O(cells · 4^L)
Space
O(total characters)
What goes wrong
Failing to restore the cell after recursion corrupts the board for every later starting position.