## Leetcode 212

Posted on 04 Mar 2017
trie

### Tutorial

Use trie to store all the words. Then we do a DFS on the board, at each step of which we check whether the current path is a prefix of some words using the trie as a prunning method.

### Solution

class TrieNode:
def __init__(self):
self.isEnd=False
self.children={}

def insert(self,word):
cur=self
for i in word:
if i not in cur.children:
cur.children[i]=TrieNode()
cur=cur.children[i]
cur.isEnd=True

class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
trie = TrieNode()
for word in words:
trie.insert(word)
n = len(board)
m = len(board[0])
self.vis = [[False for i in range(m)] for x in range(n)]
self.ans = []
for i in range(n):
for j in range(m):
self.dfs(board, i, j, [], trie)
return list(set(self.ans))

def dfs(self, board, sx, sy, st, trie):
if sx < 0 or sx >= len(board) or sy < 0 or sy >= len(board[0]):
return
if self.vis[sx][sy]:
return
if board[sx][sy] not in trie.children:
return
trie = trie.children[board[sx][sy]]

st.append(board[sx][sy])

if trie.isEnd:
self.ans.append(''.join(st))

self.vis[sx][sy] = True
self.dfs(board, sx + 1, sy, st, trie)
self.dfs(board, sx - 1, sy, st, trie)
self.dfs(board, sx, sy + 1, st, trie)
self.dfs(board, sx, sy - 1, st, trie)
self.vis[sx][sy] = False
st.pop()