LeetCode 212. [Python] Word Search II
原题链接
困难
作者:
徐辰潇
,
2021-02-20 01:45:52
,
所有人可见
,
阅读 557
class Node:
def __init__(self):
self.Dict = {}
self.isEnd = False
class Trie:
def __init__(self):
self.dummy = Node()
def insert(self, word):
head = self.dummy
for char in word:
if char not in head.Dict:
head.Dict[char] = Node()
head = head.Dict[char]
head.isEnd = True
class Solution:
#Using Trie to search prefix of given word list
#Explicitly use search API function in Question 208 can lead to TLE
#TC: O(mn*L) L: maximum length of word
#SC: Max O(KL) K: len(words)
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m = len(board)
n = len(board[0])
trie = Trie()
for word in words:
trie.insert(word)
res = []
DirList = [[0,1],[0,-1],[1,0],[-1,0]]
def dfs(x0, y0, prefix, char, Node):
if char not in Node.Dict:
return
if Node.Dict[char].isEnd:
Node.Dict[char].isEnd = False
res.append(prefix)
for Dir in DirList:
x = x0 + Dir[0]
y = y0 + Dir[1]
if 0 <= x < m and 0 <= y < n and board[x][y] != '#':
tmp = board[x][y]
board[x][y] = '#'
dfs(x, y, prefix+tmp, tmp, Node.Dict[char])
board[x][y] = tmp
for i in range(m):
for j in range(n):
Node = trie.dummy
if board[i][j] in Node.Dict:
tmp = board[i][j]
board[i][j] = '#'
dfs(i, j, tmp, tmp, Node)
board[i][j] = tmp
return res