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:
rst.add(path)
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)
Trie used Python solution O(m^2 n^2), O(1)


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