Build a trie containing all target words. Then DFS from each cell:
def findWords(board, words):
trie = buildTrie(words)
result = []
def dfs(r, c, node, path):
if node.word:
result.append(node.word)
node.word = None # avoid duplicates
if r < 0 or r >= rows or c < 0 or c >= cols:
return
char = board[r][c]
if char not in node.children:
return
board[r][c] = '#' # mark visited
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r+dr, c+dc, node.children[char], path+char)
board[r][c] = char # restore
for r in range(rows):
for c in range(cols):
dfs(r, c, trie.root, "")
return result
The trie prunes search paths early. If the current path isn't a prefix of any target word, you stop immediately.