# Python DFS Solution, beat 97%

• Typical idea using Trie and DFS

``````class TrieNode():
def __init__(self):
self.children = dict()
self.word = ""

class Trie():
def __init__(self):
self.root = TrieNode()

node = self.root
for letter in word:
if node.children.has_key(letter):
node = node.children[letter]
else:
node.children[letter] = TrieNode()
node = node.children[letter]
node.word = word

class Solution(object):
def findWords(self, G, words):
m = len(G)
if m == 0: return []
n = len(G[0])
if n == 0: return []
result = set()
# initialize a trie tree
trie = Trie()
for w in words:
# search
root = trie.root
for i in xrange(m):
for j in xrange(n):
letter = G[i][j]
if letter in root.children:
self.DFS(G, root.children[letter], i, j, result)
return list(result)

def DFS(self, G, node, i, j, res):
if node.word != "":
if node.children is None:
return
m, n = len(G), len(G[0])
back = G[i][j]
G[i][j] = '*'
if i-1 >= 0 and G[i-1][j] in node.children:
self.DFS(G, node.children[G[i-1][j]], i-1, j, res)
if i+1 < m and G[i+1][j] in node.children:
self.DFS(G, node.children[G[i+1][j]], i+1, j, res)
if j-1 >= 0 and G[i][j-1] in node.children:
self.DFS(G, node.children[G[i][j-1]], i, j-1, res)
if j+1 < n and G[i][j+1] in node.children:
self.DFS(G, node.children[G[i][j+1]], i, j+1, res)
G[i][j] = back
``````

If I change DFS helper function into following, the runtime will be doubled...

``````    def DFS(self, G, node, i, j, res):
if node.word != "":
if len(node.children) == 0:
return
m, n = len(G), len(G[0])
dir = [(-1, 0), (1, 0), (0, 1), (0, -1)]
back = G[i][j]
G[i][j] = '*'
for dx, dy in dir:
x, y = i + dx, j + dy
if x < 0 or x >= m or y < 0 or y >= n:
continue
letter = G[x][y]
if letter in node.children:
self.DFS(G, node.children[letter], x, y, res)
G[i][j] = back
``````

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