Trie

In [60]:

    

class Trie:
    def _construct(self, input_):
        for key, value in input_.items():
            base = self.trie
            for index, char in enumerate(value):
                if self._is_last(char, index, value):
                    base[char] = key
                else:
                    if char not in base:
                        base[char] = {}
                    
                base = base[char]
        
    def __init__(self, input_):
        self.trie = {}
        self._construct(input_)
        
    @staticmethod
    def _is_last(char, index, key):
        return char == '*' or index == len(key) - 1
        
    def lookup(self, input_):
        base = self.trie
        for index, char in enumerate(input_):
            try:
                if self._is_last(char, index, input_):
                    return base[char]
                else:
                    base = base[char]
            except Exception as e:
                return base


    

In [61]:

    

trie = Trie({
    'P1': '111*',
    'P2': '11*',
    'P3': '1010*',
    'P4': '10101'
})


    

In [62]:

    

trie.lookup('111*')


    

    
Out[62]:





'P1'

In [66]:

    

trie.lookup('111*')


    

    
Out[66]:





'P1'

In [65]:

    

trie.lookup('1111')


    

    
Out[65]:





{'*': 'P1'}

In [67]:

    

trie.lookup('11')


    

    
Out[67]:





{'*': 'P2', '1': {'*': 'P1'}}

In [ ]: