Build trie, DFS from each cell following trie paths.
def findWords(board, words): trie = {} for word in words: node = trie for c in word: node = node.setdefault(c, {}) node['$'] = word
result = []
m, n = len(board), len(board[0])
def dfs(i, j, node):
char = board[i][j]
if char not in node:
return
nextNode = node[char]
if '$' in nextNode:
result.append(nextNode['$'])
del nextNode['$']
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n:
dfs(ni, nj, nextNode)
board[i][j] = char
for i in range(m):
for j in range(n):
dfs(i, j, trie)
return result
Time depends on board and trie structure. Space: .