如何在表示为 python 中字典的树中搜索单词？

Question

我有一本这样的字典 -

{"a": {"b": {"e": {},
             "f": {},
             "g": {"l": {},
                   "m": {},
                   "n": {}}},
       "c": {"h": {},
             "i": {}},
       "d": {"j": {},
             "k": {}}}}

翻译成这样的树状结构

            a   
          /  |\
         /   | \
        /    |  \
       /     |   \
      /      |    \
     /       |     \
    b        c      d
  / | \      | \    |\
e   f  g     h  i   j k
      / |\  
     l  m n

我有一个字符列表 - [a, c, h, q, r] 我想查找字典中是否存在给定的单词（字符列表），如果不存在，则 return 存在从头开始最长的子序列。如果是，return 相同的列表。

在上面的例子中，return应该是 - [a, c, h]

Answer 1

编辑 - 感谢您将数据更新为有意义的内容。

遍历 trie 非常有趣。这是一个快速演示。

trie = {"a": {"b": {"e": {},
                    "f": {},
                    "g": {"l": {},
                          "m": {},
                          "n": {}}},
              "c": {"h": {},
                    "i": {}},
              "d": {"j": {},
                    "k": {}}}}

target = 'achqr'
sub_trie = trie
longest_sequence = []
for c in target:
    sub_trie = sub_trie.get(c)
    if sub_trie is None:  # the letter being looked for doesn't exist after this sequence
        break
    longest_sequence.append(c)  # track the sequence since the trie is not reverse linked
print(longest_sequence)

如何在表示为 python 中字典的树中搜索单词？

How to search for a word in a tree represented as a dictionary of dictionaries in python?

python

dictionary

trie