# Trie used Python solution O(m^2 n^2), O(1)

• ``````class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
def DFS(path, i, j, trie):
if '#' in trie:

if i < 0 or j < 0 or i > m - 1 or j > n - 1 or board[i][j] not in trie:
return
tmp = board[i][j]
board[i][j] = ord(tmp) ^ 256
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
DFS(path + tmp, x,  y, trie[tmp])
board[i][j] = tmp

if not board: return []
trie = {}
for word in words:
t = trie
for w in word:
if w not in t:
t[w] = {}
t = t[w]
t['#'] = '#'
rst = set()
m, n = len(board), len(board[0])
for i in xrange(m):
for j in xrange(n):
DFS("", i, j, trie)
return list(rst)
``````

• What does "board[i][j] = ord(tmp) ^ 256" do?

• @Skywalker-lili
It marks board[i][j] visited. Using anything other than lowercase letters will also work. I don't know he chose xor though.

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