Trie: How to implement Trie data structure with partial search in Python?

Question

I want to be able to return the count of partial words present using Tries. What would be the best way to implement this in Python?

Example:

Input
4
add hack
add hackerrank
find hac
find hak

Expected output
2
0

Please follow the link below to the problem! https://www.hackerrank.com/challenges/ctci-contacts/problem

Edit:

from collections import defaultdict
n = int(input().strip())


class Trie:

    def __init__(self):
        self.root= dict()

    def insert(self,word):
        current = self.root
        for letter in word:
            exist = False
            for (t1,t2) in current:
                if t1==letter:
                    current[(t1,t2+1)] = current.pop((t1,t2))
                    current = current[(t1,t2+1)]
                    exist = True
                    break
            if exist==False:
                current[(letter,1)] = {}
                current = current[(letter,1)]

    def search(self,word):
        current = self.root
        count = 0
        for letter in word:
            found = False
            for (t1,t2) in current:
                if t1==letter:
                    current = current[(t1,t2)]
                    found = True
                    count = t2
                    break
            if found == False:
                return 0
        return count
    def printDict(self):
        print(self.root)


for a0 in range(n):
    op, contact = input().strip().split(' ')
    T = Trie()
    if op == 'add':
        T.insert(contact)
        T.printDict()
    else:
        print(T.search(contact))

I am using Tuples as keys to the dictionaries. I know its messy but I want to store the count of the contacts as well.

Its not a competition question. Its a question from Cracking the coding interview book and I have tried using nested dictionaries, considered tuples and objects a keys but I am always getting stuck somewhere. Any help is appreciated! — Suyash, Sep 05 '17 at 13:09
https://stackoverflow.com/questions/11015320/how-to-create-a-trie-in-python — NPE, Sep 05 '17 at 13:10
Well then show code where you got stuck and explain what you've tried and what's the problem with the shown code. Otherwise the answer is: implement a Trie. But you know that already, so where is the _concrete_ problem. — BlackJack, Sep 06 '17 at 13:07
Using tuples as keys is not only messy but very unfortunate because you search in a loop through the keys. You loose the advantage of dictionaries to access a key in constant time without a linear search. The key should be just the character. The count and the children of that node are both part of the value to the key. Writing a `Node` class and using `collections.defaultdict` might make your code simpler. — BlackJack, Sep 07 '17 at 16:46
So how can I have both count and children as the value in the nested dictionary because at the next layer, the children should be the keys and count shouldn't? — Suyash, Sep 07 '17 at 17:38

Trie: How to implement Trie data structure with partial search in Python?

0 Answers0