# Python code use trie and dfs 380ms

• ``````class Solution:
# @param {character[][]} board
# @param {string[]} words
# @return {string[]}
def findWords(self, board, words):
#make trie
trie={}
for w in words:
t=trie
for c in w:
if c not in t:
t[c]={}
t=t[c]
t['#']='#'
self.res=set()
self.used=[[False]*len(board[0]) for _ in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
self.find(board,i,j,trie,'')
return list(self.res)

def find(self,board,i,j,trie,pre):
if '#' in trie:
self.res.add(pre)
if i<0 or i>=len(board) or j<0 or j>=len(board[0]):
return
if not self.used[i][j] and board[i][j] in trie:
self.used[i][j]=True
self.find(board,i+1,j,trie[board[i][j]],pre+board[i][j])
self.find(board,i,j+1,trie[board[i][j]],pre+board[i][j])
self.find(board,i-1,j,trie[board[i][j]],pre+board[i][j])
self.find(board,i,j-1,trie[board[i][j]],pre+board[i][j])
self.used[i][j]=False``````

• Really nice way to build trie(). For space saving purpose, I rewrite your code in which way we don't need the "self.used" global variable:

``````def findWords(self, board, words):
trie = {}
for w in words:
t = trie
for c in w:
if c not in t:
t[c] = {}
t = t[c]
t['#'] = '#'
res = []
for i in range(len(board)):
for j in range(len(board[0])):
self.find(board, i, j, trie, '', res)
return list(set(res))

def find(self, board, i, j, trie, path, res):
if '#' in trie:
res.append(path)
if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or board[i][j] not in trie:
return
tmp = board[i][j]
board[i][j] ="@"
self.find(board, i+1, j, trie[tmp], path+tmp, res)
self.find(board, i, j+1, trie[tmp], path+tmp, res)
self.find(board, i-1, j, trie[tmp], path+tmp, res)
self.find(board, i, j-1, trie[tmp], path+tmp, res)
board[i][j] = tmp``````

• board[i] is a string ,'board[i][j] ="@" 'is not be supported.

• indeed, the way of building trie saves a lot of time.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.