leetcode/python/0212-word-search-ii.py at main · ColstonBod-oy/leetcode · GitHub

Name: leetcode/python/0212-word-search-ii.py at main · ColstonBod-oy/leetcode · GitHub
Rating: 4.8 (8941 reviews)
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
classTrieNode:
def__init__(self):
self.children= {}
self.isWord=False
self.refs=0

defaddWord(self, word):
cur=self
cur.refs+=1
forcinword:
ifcnotincur.children:
cur.children[c] =TrieNode()
cur=cur.children[c]
cur.refs+=1
cur.isWord=True

defremoveWord(self, word):
cur=self
cur.refs-=1
forcinword:
ifcincur.children:
cur=cur.children[c]
cur.refs-=1


classSolution:
deffindWords(self, board: List[List[str]], words: List[str]) ->List[str]:
root=TrieNode()
forwinwords:
root.addWord(w)

ROWS, COLS=len(board), len(board[0])
res, visit=set(), set()

defdfs(r, c, node, word):
if (
rnotinrange(ROWS)
orcnotinrange(COLS)
orboard[r][c] notinnode.children
ornode.children[board[r][c]].refs<1
or (r, c) invisit
 ):
return

visit.add((r, c))
node=node.children[board[r][c]]
word+=board[r][c]
ifnode.isWord:
node.isWord=False
res.add(word)
root.removeWord(word)

dfs(r+1, c, node, word)
dfs(r-1, c, node, word)
dfs(r, c+1, node, word)
dfs(r, c-1, node, word)
visit.remove((r, c))

forrinrange(ROWS):
forcinrange(COLS):
dfs(r, c, root, "")

returnlist(res)