无法编写函数来检索 trie 中的所有单词

Question

我有以下 Trie 实现：

class TrieNode:
    def __init__(self):
        self.nodes = defaultdict(TrieNode)
        self.is_fullpath = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        curr = self.root
        for char in word:
            curr = curr.nodes[char]
        curr.is_fullpath = True

我正在尝试编写一种方法来检索我的 trie 中所有单词的列表。

t = Trie()
t.insert('a')
t.insert('ab')
print(t.paths())  # ---> ['a', 'ab']

我当前的实现如下所示：

def paths(self, node=None):
    if node is None:
        node = self.root
    result = []
    for k, v in node.nodes.items():
        if not node.is_fullpath:
            for el in self.paths(v):
                result.append(str(k) + el)
        else:
            result.append('')
    return result

但似乎没有return完整的单词列表。

Answer 1

您的代码中存在以下问题：

当is_fullpath 为True 时，不再进一步查找。但在那种情况下，你应该也看得更深（对于更长的单词）。
它不应该检查 node.is_fullpath 但 v.is_fullpath.
result.append('') 不正确。应该是result.append(str(k))

因此您的 for 循环体可能如下所示：

if v.is_fullpath:
    result.append(str(k))
for el in self.paths(v):
    result.append(str(k) + el)

但是我会这样做：

在您的 TrieNode class:

上定义此递归生成器方法

def paths(self, prefix=""):
    if self.is_fullpath:
        yield prefix
    for chr, node in self.nodes.items():
        yield from node.paths(prefix + chr)

注意这是如何将路径上收集的字符传递给递归调用的。如果 is_fullpath 布尔值在任何时候为 True，我们就会产生该路径。我们总是通过子节点递归地继续搜索。

Trieclass上的方法就很简单了：

def paths(self):
    return list(self.root.paths())

无法编写函数来检索 trie 中的所有单词

Cannot write a function to retrieve all words in a trie

python

trie

data-structures