Return Trie中的字符串

Question

我有这个 Trie：

                a
               / \
              b   c
             / \   \
            t   y   u
           2     5   3
numbers at leaf stands for frequency, stored at the terminal node

而且我有默认的 Trie 搜索函数来搜索字符串。当我执行 search('a') 时，它将 return aby 因为它是最常插入的字符串。频率由 self.count 存储在我的函数中。我不想 post 我的代码。

您将如何解决和 returning 从 a 到 y 的节点？提前谢谢你。

Answer 1

您可以使用递归生成器函数遍历 trie 并生成包含搜索值作为子字符串的所有字符串：

简单的 trie 设置：

class Trie:
   def __init__(self, l=None):
      self.l, self.count, self.tree = l, 0, []
   def insert_l(self, word):
      if word:
         if not (n:=[i for i in self.tree if i.l == word[0]]):
            self.tree.append(Trie(word[0]))
            self.tree[-1].add_word(word)
         else:
            n[-1].add_word(word)
   def add_word(self, word):
      if self.l is not None:
         self.count += 1
      self.insert_l(word if self.l is None else word[1:])

现在，search方法可以添加到Trie:

class Trie:
    ...
    def search(self, word):
      def _search(t, c = []):
         if not t.tree:
            yield c+[t]
         else:
            for i in t.tree:
              yield from _search(i, c if t.l is None else c+[t])
      if (l:=[(j, i) for i in _search(self) if word in (j:=''.join(k.l for k in i))]):
         return max(l, key=lambda x:x[-1][-1].count)[0]

t = Trie()
words = ['abt', 'abt', 'aby', 'aby', 'aby', 'aby', 'aby', 'acu', 'acu', 'acu']
for word in words:
   t.add_word(word)

print(t.search('a'))

输出：

'aby'

Return Trie中的字符串

Return the string in Trie

python

trie