-1

I have a dictionary of words like this - 

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

It's a tree like structure that translates like this

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

And I have a list of characters - [a, c, h, q, r] I want to find if the given word(the list of characters) exist in the dictionary and if it doesn't, return the longest sub-sequence from the beginning that exists. If it does, return the same list.

In the above example, the return should be - [a, c, h]

KobeJohn
  • 7,390
  • 6
  • 41
  • 62
user1844124
  • 23
  • 5
  • Do you look up for characters in the dictionary regardless of they're keys or values? – u354356007 Sep 03 '15 at 04:55
  • I'm guessing you are getting downvotes for not showing any code attempt at solving the problem. Also the dictionary formatting is pretty unusual. Is that supposed to be `e, f, g` as a tuple? What is `{j, k}` supposed to be because the way it is written is a `set` not a `dict`. – KobeJohn Sep 03 '15 at 04:55

1 Answers1

1

edit - thank you for updating the data to something that makes sense.

Traversing a trie is pretty interesting. Here is a quick demonstration.

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)
KobeJohn
  • 7,390
  • 6
  • 41
  • 62
  • 1
    `sub_trie.get(c)` can be used instead of `try except` if one doesn't want to deal with exceptions. – u354356007 Sep 03 '15 at 05:21
  • This does solve my problem. But I was hoping there would be something cleaner to do along the lines of intersection of list and dictionary "trie.keys() & target" I guess not – user1844124 Sep 03 '15 at 07:46
  • If you make a function of it, it will take just one line in your main code. Python doesn't have trees built in directly but there are [plenty of libraries](http://stackoverflow.com/questions/2442014/tree-libraries-in-python) out there if you need more complex operations. – KobeJohn Sep 03 '15 at 07:57