-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
212.py
79 lines (71 loc) · 2.88 KB
/
212.py
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
__________________________________________________________________________________________________
sample 156 ms submission
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
if not board or not board[0]: return False
R, C = len(board), len(board[0])
root = {}
for word in words:
trie = root
for c in word:
if c not in trie:
trie[c] = {}
trie = trie[c]
trie['#'] = word
def dfs(i, j, parent):
c, board[i][j] = board[i][j], '{'
trie = parent[c]
if '#' in trie:
ans.add(trie['#'])
trie.pop('#')
if i and board[i - 1][j] in trie:
dfs(i - 1, j, trie)
if i < R - 1 and board[i + 1][j] in trie:
dfs(i + 1, j, trie)
if j and board[i][j - 1] in trie:
dfs(i, j - 1, trie)
if j < C - 1 and board[i][j + 1] in trie:
dfs(i, j + 1, trie)
board[i][j] = c
if not trie:
parent.pop(c)
ans = set()
for i in range(R):
for j in range(C):
if board[i][j] in root:
dfs(i, j, root)
return list(ans)
__________________________________________________________________________________________________
sample 27988 kb submission
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
trie = lambda: collections.defaultdict(trie)
root = trie()
for word in words:
cur = root
for letter in word:
cur = cur[letter]
cur['END'] = True
ret = set()
for i in range(len(board)):
for j in range(len(board[0])):
self.dfsHelper(root, i, j, "", ret, board)
# print(root['a']['a']['a']['b'])
return list(ret)
def dfsHelper(self, node, i, j, path, ret, board):
if node.get('END', False) == True:
ret.add(path)
node['END'] = False
if 0 <= i < len(board) and 0 <= j < len(board[0]) and board[i][j] != '#':
# print(i, j, path)
letter = board[i][j]
if letter not in node.keys() or not node.keys():
return
# node = node[letter]
board[i][j] = '#'
self.dfsHelper(node[letter], i+1, j, path + letter, ret, board)
self.dfsHelper(node[letter], i-1, j, path + letter, ret, board)
self.dfsHelper(node[letter], i, j+1, path + letter, ret, board)
self.dfsHelper(node[letter], i, j-1, path + letter, ret, board)
board[i][j] = letter
__________________________________________________________________________________________________