Как искать слово в дереве, представленное в виде словаря словарей в 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

---

редактировать - спасибо за обновление данных до чего-то, что имеет смысл.

---

Пройдя через три, это довольно интересно. Вот быстрая демонстрация.

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)