Python `collections.defaultdict` 相同 class

Question

我尝试使用 Trie 数据结构来解决一些编码问题。对于 trie 中的每个节点，您通常会放置一个其子节点的引用列表。因此，我考虑过如果查找中不存在某些子节点，则使用 defaultdict 创建一个默认的空 trie 节点。但是，我不知道如何使用 defaultdict 来引用包含它的 class。

我试了两种方法，都失败了。以下是我试过的。

from dataclasses import dataclass
from collections import defaultdict

@dataclass   
class TrieNode():
    is_word = False
    children = defaultdict("TrieNode")

上面的代码产生

Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
  File "<stdin>", line 4, in TrieNode
TypeError: first argument must be callable or None

@dataclass   
class TrieNode():
    is_word = False
    children = defaultdict(TrieNode)

以上会产生

Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
  File "<stdin>", line 4, in TrieNode
NameError: name 'TrieNode' is not defined

我的问题是关于您如何使用 defaultdict 来优雅地实现它。非常感谢您。

Answer 1

你使用 children = defaultdict(TrieNode) 的第二种方法更接近正确，因为 defaultdict 需要 TrieNode 的构造函数以便用 TrieNodes 填充它 - 另一种方法在需要可调用对象的地方传递一个字符串。您的问题是由于您在 class 完成创建之前访问名称 TrieNode，给出 NameError。要解决此问题，您可以使用 children = defaultdict(lambda: TrieNode())。这样，只有在调用 lambda 函数时才会查找名称 TrieNode。

但是，对于一个 trie，您希望每个节点都有自己的子字典，使用这种方法，修改一个节点的子字典会为所有节点修改它，因为它们的所有字典都是同一个对象.我建议您使用 dataclass.field 为每个 TrieNode 创建一个新字典，如下所示：

from dataclasses import dataclass, field
from collections import defaultdict

@dataclass   
class TrieNode():
    is_word = False
    children : 'TrieNode' = field(default_factory=lambda: defaultdict(TrieNode))

Python `collections.defaultdict` 相同 class

Python `collections.defaultdict` for the same class

python

trie

defaultdict