Given a Dictionary with user_id and a list of alert_words (words and phrases too look for in an sentence) and a string content. We have to look if the alert_words appears in the content and return the list of user_ids who's alert_words appears in the content


input = { 1 : ['how are you'], 2 : ['you are'] }

content = 'hello, how are you'

output = [1]

user_id = 1 has 'how are you' while user_id = 2 has the words but not in the correct order so only user 1 is returned.


I'm using Google's pygtrie implementation of Trie data structure to achieve this. [pygtrie documentation]


  • For each word in the given sentence
  • Check if the word is a key, if yes add it to the list of user_ids
  • check if the word has a subtrie i.e. that current word is the starting of a alert_word. So add it to another set alert_phrases
  • for each word in alert_phrases we check if we can extent with the current word and do the same set of operations if it is a key/subtrie


import pygtrie
from typing import Dict, List, Set

def build_trie(realm_alert_words : Dict[int, List[int]]) -> pygtrie.StringTrie:
    trie = pygtrie.StringTrie()
    for user_id, words in realm_alert_words.items():
        for word in words:
            alert_word = trie._separator.join(word.split())        
            if trie.has_key(alert_word):
                user_ids_for_word = trie.get(alert_word)
                trie[alert_word] = set([user_id])
    return trie

def get_user_ids_with_alert_words(trie : pygtrie.StringTrie, content : str) -> Set[int]:
    """Returns the list of user_id's who have alert_words present in content"""
    content_words = content.split()
    alert_phrases = set()
    user_ids_in_messages = set()
    for possible_alert_word in content_words:
        #has_node returns 1(HAS_VALUE) if the exact key is found, 2(HAS_SUBTRIE) if the key is a sub trie, 
        # 3 if it's both 0 if it's none 

        alert_word_in_trie = trie.has_node(possible_alert_word)
        if alert_word_in_trie & pygtrie.Trie.HAS_VALUE:
            user_ids = trie.get(possible_alert_word)

        deep_copy_alert_phrases = set(alert_phrases)

        # Check if extending the phrases with the current word in content is a subtrie or key. And
        # Remove the word if it is not a subtrie as we are interested only in continuos words in the content
        for alert_phrase in deep_copy_alert_phrases:
            extended_alert_phrase = alert_phrase + trie._separator + possible_alert_word
            alert_phrase_in_trie = trie.has_node(extended_alert_phrase)

            if alert_phrase_in_trie & pygtrie.Trie.HAS_VALUE:
                user_ids = trie.get(extended_alert_phrase)

            if alert_phrase_in_trie & pygtrie.Trie.HAS_SUBTRIE:

        if alert_word_in_trie & pygtrie.Trie.HAS_SUBTRIE:

    return user_ids_in_messages


input = {1 : ['hello'], 7 : ['this possible'], 2 : ['hello'], 3 : ['hello'], 5 : ['how are you'], 6 : ['hey']}
alert_word_trie = build_trie(input)
content = 'hello how is this possible how are you doing today'
result  = get_user_ids_with_alert_words(alert_word_trie, content)
assert(result == set([1, 2, 3, 5, 7]))

input = {1 : ['provisioning', 'Prod deployment'], 2 : ['test', 'Prod'], 3 : ['prod'], 4 : ['deployment'] }
alert_word_trie = build_trie(input)
content = 'Hello, everyone. Prod deployment has been completed'
result  = get_user_ids_with_alert_words(alert_word_trie, content)
assert(result == set([1, 2, 4]))

input = {1 : ['provisioning/log.txt'] }
alert_word_trie = build_trie(input)
content = 'Hello, everyone. Errors logged at provisioning/log.txt '
result  = get_user_ids_with_alert_words(alert_word_trie, content)
assert(result == set([1]))

The two methods are part of a larger classes which have some not so related code. You get a list of user_ids and their alert_words from the database and you process every message content based on the trie already build up.

This is for a chat application so frequency of running the get_user_id_with_alert_words is high when the build_trie is relatively less since it will be cached.

  • \$\begingroup\$ If content is Hello, how [some words] are [more words] you, what the result should be? \$\endgroup\$
    – vnp
    Jan 12, 2019 at 22:16
  • \$\begingroup\$ @Carcigenicate you solution iterates the entire alert_words which grows in size as users increase. Also i don't think the in a list is of linear time complexity. \$\endgroup\$
    – thebenman
    Jan 13, 2019 at 5:23
  • 1
    \$\begingroup\$ @thebenman: in is O(n) for lists (and strings): wiki.python.org/moin/TimeComplexity \$\endgroup\$
    – Graipher
    Jan 13, 2019 at 9:13
  • \$\begingroup\$ Since the time complexity is important to you, what do you think is the time complexity of using Tries? \$\endgroup\$
    – Graipher
    Jan 13, 2019 at 9:14
  • 1
    \$\begingroup\$ @Graipher Finding a word in a trie is O(m) where m is the length of the word and finding it in a list would be O(n) where n is the total number of elements in the list which can grow as opposed to the number of words in the message. \$\endgroup\$
    – thebenman
    Jan 13, 2019 at 11:56

1 Answer 1


This code cannot be correct.

In the function get_user_ids_with_alert_words() you define the empty set

alert_phrases = set()

You then make a copy of the empty set.

deep_copy_alert_phrases = set(alert_phrases)

And do a for loop over the this empty set.

for alert_phrase in deep_copy_alert_phrases:

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.