了解单词搜索2 Leetode的图形解决方案

Question

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中

Answer 1

trie是根节点，它只需要获取一次值，之后就不应该再更改。因此，在代码的开头，您有trie的初始化：

trie = {}

另一方面，变量node是一种指针，它遍历trie中的现有节点以检查其中的字母。它总是指向根，因此我们有：

node = trie

然后在循环中，它深入到trie中，要么跟随现有的子节点，要么创建一个新的子节点（如果它还不存在的话）。所有这些都发生在这一句话中：

node = node.setdefault(letter, {})

这是以下三种说法的简称：

if letter not in node:  # property letter does not yet exist here...
    node[letter] = {}  # create it, and attach a new node to it, extending trie
node = node[letter]  # move the pointer to that new node

当node遍历trie时，有时会使用新的子节点扩展现有节点，实际上我们正在改变trie中的（深层）内容。这是嵌套对象结构的典型情况：您可以使这些对象更加嵌套，而无需将任何内容直接指定给具有顶级对象的变量

示例

假设一个trie中只添加了一个单词；“酒吧”一词。发生的情况如下：

首先执行tree = {}

外部循环遍历单词。因为我们只有一个，所以只有一个迭代

然后执行node = tree。因此，我们现在对同一个空字典有两个引用：

{}  # this is: trie, and also: node

内部循环迭代三次。第一个字母是“b”

setdefault检测到node没有属性“b”，因此它创建了它。这会使node发生突变，现在从{}变为{ "b": {} }。意识到node和trie此时正在引用同一本词典，所以这也是trie的含义：

{  # this is: trie, also: node
    "b": {}
}

然后，在同一语句中，node被分配这个新属性“b”的值，即{}。现在trie和node不再是同一个引用：

{  # this is: trie
    "b": {}  # this is: node
}
 

我们进入下一个迭代。现在letter是“a”。同样，setdefault检测到node没有“a”属性（它是一个空字典），因此该属性是用一个新的空字典作为值创建的。我们了解这种情况

{  # this is: trie
    "b": {  # this is: node
        "a": {}
    }
}

同样，在同一语句中，node被分配给新创建的字典：

{  # this is: trie
    "b": {
        "a": {}  # this is: node
    }
}

同样，相同的过程在第三次迭代中添加了“r”：

{  # this is: trie
    "b": {
        "a": {
            "r": {}  # this is: node
        }
    }
}

循环结束后，执行以下语句：

node[WORD_KEY] = word  

因此，deep dictionary还获得了一个属性：

{  # this is: trie
    "b": {
        "a": {
            "r": {  # this is: node
                "$": "bar"
            }
        }
    }
}

您可以看到这个过程是如何扩展原始trie字典的。与开始时一样，它仍然是同一个dictionary，但它只是接收了一个dictionary作为值的属性，而dictionary又得到了扩展