获取 Trie 中所有路径的路径中结束词的最大数量

Question

考虑以下词语：

'a', 'ab', 'abcd', 'b', 'bcd'

将它们添加到 Trie 将导致以下表示，其中星号表示节点是尾词：

              root 
              / \
            *a  *b
            /     \
          *b       c
          /         \
         c          *d
        /
      *d

在此示例中，我们有两条路径，任何路径中的最大结束词数为 3(a, ab, abcd)。你将如何执行 DFS 以获得最大值？

这是我的 Trie 代码：

class TrieNode:

    def __init__(self):
        self.children = dict()
        self.end_word = 0

class Trie:

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

    def insert(self, key):
        current = self.root
        for char in key:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.end_word += 1

Answer 1

你可以在 TrieNode class 上添加一个方法 returns 是否是一个 end_word 加上在所有 [= 上调用相同方法的总和21=]:

class TrieNode:
    def __init__(self):
        self.children = dict()
        self.end_word = 0
    def word_count(self):
        return self.end_word + sum([word_count() for c in self.children.values() ])

使用方法：

t = Trie()
for w in ('a', 'ab', 'abcd', 'b', 'bcd'):
    t.insert(w)

t.root.word_count()
# 5

要找到最大值，只需在所有根上调用它 children 并比较：

max(branch.words() for branch in t.root.children.values())
# 3

Answer 2

你应该在你的 TrieNode 中添加一个方法，如果我理解你的问题，你想要这个 trie :

          root 
          / \
        *a  *b
        /     \
      *b       c
      / \       \
     c  *d      *d
    /   /
  *d   *e

至return 4 (a, ab, abd, abde)

你可以递归地做：

class TrieNode:

    def __init__(self):
        self.children = dict()
        self.end_word = 0

    def count_end_words(self):
        if self.children:
            return self.end_word + max(child.count_end_words() for child in self.children.values())
        return self.end_word

class Trie:

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

    def insert(self, key):
        current = self.root
        for char in key:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.end_word += 1

    def max_path_count_end_words(self):
        return self.root.count_end_words()

root = Trie()
for word in ('a', 'ab', 'abcd', 'b', 'bcd', 'abd', 'abde'):
     root.insert(word)

print(root.max_path_count_end_words()) # returns 4

如评论中所述，您可以避免创建 class TrieNode，这是一种方法：

class Trie:

    def __init__(self):
        self.children = dict()
        self.is_end_word = False

    def insert(self, key):
        current = self
        if not key:
            return
        if len(key) == 1:
            self.is_end_word = True
        char  = key[0]
        if char not in current.children:
            self.children[char] = Trie()
        return self.children[char].insert(key[1:])

    def max_path_count_end_words(self):
        if self.children:
            return self.is_end_word + max(child.max_path_count_end_words() for child in self.children.values())
        return self.is_end_word

root = Trie()
for word in ('a', 'ab', 'abcd', 'b', 'bcd', 'abd', 'abde'):
     root.insert(word)

print(root.max_path_count_end_words()) # returns 4

获取 Trie 中所有路径的路径中结束词的最大数量

Get maximum number of end words in a path for all paths in a Trie

python

trie