时间戳

首页 > 解决方案 > 了解 Word Search 2 Leetode 的 Graph 解决方案

python - 了解 Word Search 2 Leetode 的 Graph 解决方案

问题描述

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:{$:'oath'}}}}} 等）而不是尝试。但是，当我调试代码时，我看到这个数据结构同时存储在 node 和 trie 中。

标签： pythonalgorithmgraph

解决方案

trie是根节点，它只需要获取一次值，之后就不会再改变了。所以在代码的开头你有这个初始化trie：

trie = {}

node另一方面，变量是一种指针，它遍历特里树中的现有节点，以检查那里的字母。它总是开始指向根，所以我们有：

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

内部循环迭代 3 次。首先letter是“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是“一”。同样，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

因此，深度字典也获得了一个属性：

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

所以你会看到这个过程是如何扩展原始trie字典的。它仍然是同一个字典，就像一开始一样，但它只是收到了一个带有字典作为值的属性，而它又得到了扩展。

推荐阅读