I found myself not as enthusiastic as before.20200531
class Trie(object):
"""docstring for Trie"""
def __init__(self):
super(Trie, self).__init__()
self.root = {}
self.end_of_word = '#'
def insert(self, word):
node = self.root
for char in word:
# setdefault() 和 get() 类似, 如果键不存在,将会添加键并将值设为默认值。
# dict.setdefault(key, default=None)
node = node.setdefault(char,{})
node[self.end_of_word] = self.end_of_word
def search(self, word):
node = self.root
for char in node:
if char not in node:
return False
node = node[char]
return self.end_of_word in node
def start_with(self, prefix):
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True
题目描述:
https://leetcode-cn.com/problems/word-search-ii/
def findWords(board, words):
res = set()
rows = len(board)
cols = len(board[0])
# create trie
root = {}
for word in words:
node = root
for char in word:
node = node.setdefault(char, {})
node['#'] = '#'
# dfs
def dfs(i, j, board, cur_word, cur_dic):
char = board[i][j]
if char not in cur_dic:
return
cur_word += char
cur_dic = cur_dic[char]
# terminate condition
if '#' in cur_dic:
res.add(cur_word)
# current deal
tmp, board[i][j] = board[i][j],'0'
# drill down
for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
i_ = i + dx
j_ = j + dy
if 0 <= i_< rows and 0<=j_<cols and board[i_][j_]!='0':
dfs(i_, j_, board, cur_word, cur_dic)
# recover
board[i][j] = tmp
for i in range(rows):
for j in range(cols):
if board[i][j] not in root:
continue
dfs(i, j, board, '', root)
return list(res)
结果生成过程:
root
示意图
{
'o': {
'a': {
't': {
'h': {
'#': '#'
}
}
}
},
'p': {
'e': {
'a': {
'#': '#'
}
}
},
'e': {
'a': {
't': {
'#': '#'
}
}
},
'r': {
'a': {
'i': {
'n': {
'#': '#'
}
}
}
}
}
![](https://img.haomeiwen.com/i2013561/c25f983194bc643d.png)
Done
网友评论