@@ -2,64 +2,65 @@ class TrieNode:
22def __init__ (self ):
33self .children = {}
44self .isWord = False
5- self .refs = 0
5+
6+ class Trie :
7+ def __init__ (self ):
8+ self .root = TrieNode ()
69
710def addWord (self ,word ):
8- cur = self
9- cur .refs += 1
11+ current = self .root
1012for c in word :
11- if c not in cur .children :
12- cur .children [c ]= TrieNode ()
13- cur = cur .children [c ]
14- cur .refs += 1
15- cur .isWord = True
13+ if c not in current .children :
14+ current .children [c ]= TrieNode ()
15+ current = current .children [c ]
16+ current .isWord = True
1617
1718def removeWord (self ,word ):
18- cur = self
19- cur . refs -= 1
20- for c in word :
21- if c in cur .children :
22- cur = cur . children [ c ]
23- cur . refs -= 1
19+ node = self . root
20+ path = [( None , node )]
21+ for char in word :
22+ node = node .children [ char ]
23+ path . append (( char , node ))
24+ node . isWord = False
2425
26+ for i in range (len (path )- 1 ,0 ,- 1 ):
27+ char ,currNode = path [i ][0 ],path [i ][1 ]
28+ parentNode = path [i - 1 ][1 ]
29+ if currNode .isWord or currNode .children :
30+ break
31+ del parentNode .children [char ]
2532
2633class Solution :
2734def findWords (self ,board :List [List [str ]],words :List [str ])-> List [str ]:
28- root = TrieNode ()
29- for w in words :
30- root .addWord (w )
35+ trie = Trie ()
3136
32- ROWS ,COLS = len (board ),len (board [0 ])
33- res ,visit = set (),set ()
37+ # Converting words list to a trie
38+ for word in words :
39+ trie .addWord (word )
40+
41+ rows ,columns = len (board ),len (board [0 ])
42+ result ,visit = set (),set ()
3443
3544def dfs (r ,c ,node ,word ):
36- if (
37- r < 0
38- or c < 0
39- or r == ROWS
40- or c == COLS
41- or board [r ][c ]not in node .children
42- or node .children [board [r ][c ]].refs < 1
43- or (r ,c )in visit
44- ):
45+ if (r < 0 or c < 0 or
46+ r == rows or c == columns or
47+ board [r ][c ]not in node .children or (r ,c )in visit ):
4548return
4649
4750visit .add ((r ,c ))
4851node = node .children [board [r ][c ]]
4952word += board [r ][c ]
5053if node .isWord :
51- node .isWord = False
52- res .add (word )
53- root .removeWord (word )
54+ result .add (word )
55+ trie .removeWord (word )
5456
5557dfs (r + 1 ,c ,node ,word )
5658dfs (r - 1 ,c ,node ,word )
5759dfs (r ,c + 1 ,node ,word )
5860dfs (r ,c - 1 ,node ,word )
5961visit .remove ((r ,c ))
6062
61- for r in range (ROWS ):
62- for c in range (COLS ):
63- dfs (r ,c ,root ,"" )
64-
65- return list (res )
63+ for r in range (rows ):
64+ for c in range (columns ):
65+ dfs (r ,c ,trie .root ,"" )
66+ return list (result )