1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
row = len(board)
col = len(board[0])
trie = Trie()
# 把words里的单词插入TRIE
for word in words:
trie.insert(word)
# 用来记录这个坐标是否被访问
visited = [[False] * col for x in range(row)]
# 用来控制方向
dz = zip([1,0,-1,0],[0,1,0,-1])
ret = []
# 深度优先遍历board
def dfs(word,node,x,y):
node = node.children.get(board[x][y])
# 这个坐标不是TRIE中当前node的资节点
if node is None:
return
visited[x][y] = True
# 深度遍历board，直到某个坐标不在Trie中
for z in dz:
nx, ny = x+z[0], y+z[1]
if nx >=0 and nx <row and ny >= 0 and ny < col and not visited[nx][ny]:
dfs(word+board[nx][ny], node,nx,ny)
# 若发现word
if node.isWord == True:
ret.append(word)
trie.delete(word)
visited[x][y] = False
# 主函数开始
for x in range(row):
for y in range(col):
dfs(board[x][y], trie.root,x,y)
return sorted(ret)
class TrieNode(object):
def __init__(self):
self.isWord = False
self.children = dict()
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for letter in word:
child = node.children.get(letter)
if not child:
child = TrieNode()
node.children[letter] = child
node = child
node.isWord = True
def delete(self, word):
node = self.root
queue = [] # <letter:node> 记录要删除哪些node
for letter in word:
queue.append((letter,node))
child = node.children.get(letter)
# 要删除的word不在tri中
if child is None:
return False
node = child
# 要删除的word在tri中，但不是一个词
if node.isWord == False:
return False
# 要删除的word找到，且这个节点有儿子
if len(node.children):
node.isWord = False
else:
# 最复杂的情况，要删除的节点没有字节点，需要按照queue的轨迹依次往上删除
for letter, node in reversed(queue):
del node.children[letter]
# 要一直删除直到某个节点有儿子，或者他是词
if len(node.children) or node.isWord:
break
return True
|