class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
WORD_KEY = '$'
trie = {}
for word in words:
node = trie
for letter in word:
# retrieve the next node; If not found, create a empty node.
node = node.setdefault(letter, {})
# mark the existence of a word in trie node
node[WORD_KEY] = word
rowNum = len(board)
colNum = len(board[0])
matchedWords = []
def backtracking(row, col, parent):
letter = board[row][col]
currNode = parent[letter]
# check if we find a match of word
word_match = currNode.pop(WORD_KEY, False)
if word_match:
# also we removed the matched word to avoid duplicates,
# as well as avoiding using set() for results.
matchedWords.append(word_match)
# Before the EXPLORATION, mark the cell as visited
board[row][col] = '#'
# Explore the neighbors in 4 directions, i.e. up, right, down, left
for (rowOffset, colOffset) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
newRow, newCol = row + rowOffset, col + colOffset
if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:
continue
if not board[newRow][newCol] in currNode:
continue
backtracking(newRow, newCol, currNode)
# End of EXPLORATION, we restore the cell
board[row][col] = letter
# Optimization: incrementally remove the matched leaf node in Trie.
if not currNode:
parent.pop(letter)
for row in range(rowNum):
for col in range(colNum):
# starting from each of the cells
if board[row][col] in trie:
backtracking(row, col, trie)
return matchedWords
我不明白trie是如何存储数据结构的。从片段中:
for word in words:
node = trie
for letter in word:
# retrieve the next node; If not found, create a empty node.
node = node.setdefault(letter, {})
# mark the existence of a word in trie node
node[WORD_KEY] = word
节点应该存储数据结构(例如{o:{a:{t:{h:{$:'ware'}}等),而不是trie。然而,当我调试代码时,我看到这个数据结构同时存储在node和trie中
trie
是根节点,它只需要获取一次值,之后就不应该再更改。因此,在代码的开头,您有trie
的初始化:另一方面,变量
node
是一种指针,它遍历trie中的现有节点以检查其中的字母。它总是指向根,因此我们有:然后在循环中,它深入到trie中,要么跟随现有的子节点,要么创建一个新的子节点(如果它还不存在的话)。所有这些都发生在这一句话中:
这是以下三种说法的简称:
当
node
遍历trie时,有时会使用新的子节点扩展现有节点,实际上我们正在改变trie
中的(深层)内容。这是嵌套对象结构的典型情况:您可以使这些对象更加嵌套,而无需将任何内容直接指定给具有顶级对象的变量示例
假设一个trie中只添加了一个单词;“酒吧”一词。发生的情况如下:
首先执行
tree = {}
外部循环遍历单词。因为我们只有一个,所以只有一个迭代
然后执行
node = tree
。因此,我们现在对同一个空字典有两个引用:内部循环迭代三次。第一个字母是“b”
setdefault
检测到node
没有属性“b”,因此它创建了它。这会使node
发生突变,现在从{}
变为{ "b": {} }
。意识到node
和trie
此时正在引用同一本词典,所以这也是trie
的含义:然后,在同一语句中,
node
被分配这个新属性“b”的值,即{}
。现在trie
和node
不再是同一个引用:我们进入下一个迭代。现在
letter
是“a”。同样,setdefault
检测到node
没有“a”属性(它是一个空字典),因此该属性是用一个新的空字典作为值创建的。我们了解这种情况同样,在同一语句中,
node
被分配给新创建的字典:同样,相同的过程在第三次迭代中添加了“r”:
循环结束后,执行以下语句:
因此,deep dictionary还获得了一个属性:
您可以看到这个过程是如何扩展原始
trie
字典的。与开始时一样,它仍然是同一个dictionary,但它只是接收了一个dictionary作为值的属性,而dictionary又得到了扩展相关问题 更多 >
编程相关推荐