如何在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]我想要查找给定的单词(字符列表)是否存在于字典中，如果不存在，则返回从开始存在的最长子序列。如果是，则返回相同的列表。

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

Answer 1

---

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

---

遍历一个tree非常有趣。下面是一个快速的演示。

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)