212. Word Search II
这道题分了两个层次，一个是要search word，第二个是要用Trie。基本上算是会做吧，但是达不到bug free的程度。
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
m = len(board)
n = len(board[0])
res = []
words = set(words)
root = TrieNode("")
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode(c)
node = node.children[c]
node.stop = True
node.word = word
res = []
for i in range(m):
for j in range(n):
visited = [[False for _ in range(n)] for _ in range(m)]
self.find(board, visited, root, res, i, j)
return res
def find(self, board, visited, root, res, i, j):
if root.stop:
if root.word not in res:
res.append(root.word)
if 0 >i or i >= len(board) or 0 > j or j >= len(board[0]) or visited[i][j]:
return
if board[i][j] in root.children:
visited[i][j] = True
for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
self.find(board, visited, root.children[board[i][j]], res, x, y)
visited[i][j] = False
class TrieNode(object):
def __init__(self, c):
self.c = c
self.stop = False
self.word = None
self.children = {}
