-
Notifications
You must be signed in to change notification settings - Fork 461
Expand file tree
/
Copy path212_Word_Search_II.py
More file actions
123 lines (103 loc) · 3.7 KB
/
Copy path212_Word_Search_II.py
File metadata and controls
123 lines (103 loc) · 3.7 KB
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# Getting "Maximum recursion depth exceeded. WHy the fuck? Did't wunderstand why
from collections import defaultdict
class TrieNode:
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False
self.fullWord = None
class Trie:
def __init__(self):
self.root = TrieNode()
def addWords(self, words):
for word in words:
currentNode = self.root
for char in word:
if not currentNode.children[char]:
currentNode.children[char] = TrieNode()
currentNode = currentNode.children[char]
currentNode.isWord = True
currentNode.fullWord = word
def searchWord(self, word):
cirrentWord = self.root
for char in word:
if not cirrentWord.children[char]:
return False
cirrentWord = cirrentWord.children[char]
return True
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
allWord = []
trie = Trie()
trie.addWords(words)
for row in range(len(board)):
for col in range(len(board[0])):
self.searchBoardDFS(board, row, col, trie.root, allWord)
return allWord
def searchBoardDFS(self, board, row, col, currentNode, allWord):
if currentNode.isWord:
allWord.append(currentNode.fullWord)
currentNode.isWord = False # to prevent from adding duplicate word
if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):
return
currentChar = board[row][col]
currentNode = currentNode.children[currentChar]
if not currentNode: # currentChar doesn't exist
return
board[row][col] = "#" # to prevent going into loop and revisiting
self.searchBoardDFS(board, row+1, col, currentNode, allWord)
self.searchBoardDFS(board, row-1, col, currentNode, allWord)
self.searchBoardDFS(board, row, col+1, currentNode, allWord)
self.searchBoardDFS(board, row, col-1, currentNode, allWord)
board[row][col] = currentChar # Backtrack
# https://tinyurl.com/y7td7eag
class TrieNode():
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False
class Trie():
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for w in word:
node = node.children[w]
node.isWord = True
def search(self, word):
node = self.root
for w in word:
node = node.children.get(w)
if not node:
return False
return node.isWord
class Solution(object):
def findWords(self, board, words):
res = []
trie = Trie()
node = trie.root
for w in words:
trie.insert(w)
for i in range(len(board)):
for j in range(len(board[0])):
self.dfs(board, node, i, j, "", res)
return res
def dfs(self, board, node, i, j, path, res):
if node.isWord:
res.append(path)
node.isWord = False
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
return
tmp = board[i][j]
node = node.children.get(tmp)
if not node:
return
board[i][j] = "#"
self.dfs(board, node, i + 1, j, path + tmp, res)
self.dfs(board, node, i - 1, j, path + tmp, res)
self.dfs(board, node, i, j - 1, path + tmp, res)
self.dfs(board, node, i, j + 1, path + tmp, res)
board[i][j] = tmp