Building a trie out of strings but 'str' object cannot be assigned error for some of the characters?

Question

I am trying to create a trie out of a list of words ["Patrick",'Pete','Peter'].

Why does the below code return {}? And how do I print the trie itself after building it?

def trieSetUpForWords(words):
    trie = {}
    for word in range(len(words)):
        currentWord = words[word]
        for char in range(len(currentWord)):
            currentLetter = currentWord[char]
            if currentLetter not in trie:
                trie[currentLetter] = {}
            trie = trie[currentLetter]

    return trie


print(trieSetUpForWords(["Patrick",'Pete','Peter']))

After each word you need to assign `trie` back to the "root" (not sure what `trie = "*"` is all about?) — Iain Shelvington, Jan 01 '22 at 13:19
Why do you need this `trie = "*"` ? After one iteration you essentially throw away the whole dictionary and assign a string to the `trie` variable. — Ervin Szilagyi, Jan 01 '22 at 13:20
Ohh okay, trie = "*" is meant to mark the end of a word. Or that's what it's meant to do. Otherwise how do I mark the end of a word, or is this not necessary to do this? — Patrick_Chong, Jan 01 '22 at 13:47
That solved the problem, thanks both! But would be good to know how to mark the end of a word? And how can I print(trie) at the end to see what it looks like? Because doing print(trie) at the end simply prints {}. — Patrick_Chong, Jan 01 '22 at 13:48

score 1 · Accepted Answer · answered Jan 01 '22 at 20:52

In order to return the trie, you may want to store the root somewhere safe and return that:

def trie_setup_for_words(words):
    root = {}
    trie = root
    for current_word in words:
        for current_letter in current_word:
            if current_letter not in trie:
                trie[current_letter] = {}
            trie = trie[current_letter]

        # Mark the end of a word
        trie['*'] = '*'

        # The root is also needed to reset it when a new word is added
        trie = root

    # Return the root here, not just the last leaf
    return root

if __name__ == "__main__":
    trie = trie_setup_for_words(["Patrick", 'Pete', 'Peter'])

If we print out the trie, we will see something like:

{'P': {'a': {'t': {'r': {'i': {'c': {'k': {'*': '*'}}}}}}, 'e': {'t': {'e': {'*': '*', 'r': {'*': '*'}}}}}}

Just to make sure out trie is constructed correctly, we may want to test out if a word exits in the trie:

def contains_word(trie: dict, word: str):
    if not word and '*' in trie:
        return True
    if word and word[0] in trie:
        return contains_word(trie[word[0]], word[1:])
    return False

This will return the following results:

print(contains_word(trie, "Patrick")) # Prints True
print(contains_word(trie, "Patric")) # Prints False
print(contains_word(trie, "Pete")) # Prints True
print(contains_word(trie, "Peter")) # Prints True
print(contains_word(trie, "Pet")) # Prints False

Thanks for the solution Ervin- could you help here please: https://stackoverflow.com/questions/70593719/why-is-the-root-different-for-the-same-character-in-my-trie-set-up-and-how-can — Patrick_Chong, Jan 05 '22 at 13:31
I tried to set it up as you have with if __name__ = "__main__" but it doesn't seem to work for the printing. And also the set up doesn't seem to be right for my code! — Patrick_Chong, Jan 05 '22 at 13:32

Building a trie out of strings but 'str' object cannot be assigned error for some of the characters?

1 Answers1