无法在 trie 遍历中重置字典指针

Question

当我尝试运行 add_word 方法时（它被简化为关注出现问题的区域），我运行陷入了一个奇怪的问题。如果我尝试将单词 "mud" 添加到 trie，节点将成功创建，但它们的 children 除外。出于某种原因，我的所有节点共享相同的 children 字典，我不知道是什么原因造成的。每当我向 trie 添加一个新字母时，我都会创建一个新的 TrieNode，这应该为每个 child 提供一个独立的 children 字典。我正在使用 python 3.5 知道我在哪里弄乱了我的指针吗？

class Trie:
    """Simple Trie Datastructure"""
    def __init__(self, root_val=""):
        self.root = TrieNode(root_val)

    def add_word(self, string):
        current = self.root
        for letter in string:
            new_entry = TrieNode(letter)
            current.children[letter] = new_entry
            current = new_entry

class TrieNode:
    """A Trie Node"""
    def __init__(self, data, children={}):
        self.data = data
        self.children = children

Answer 1

罪魁祸首在你的 TrieNode __init__ 中。将默认参数设置为 dict/list 将导致所有不带参数的调用都使用相同的实例。最简单的解决方案是将方法更改为 def __init__(self, data, children=None): 并将分配更改为 self.children = {} if children is None else children

无法在 trie 遍历中重置字典指针

Unable to reset dictionary pointer in trie traversal

python

iteration

loops