用字符串构建一个 trie 但 'str' object cannot be assigned error for some of the characters？

Question

我正在尝试从单词列表 ["Patrick",'Pete','Peter'] 中创建一个 trie。

为什么下面的代码return {}？构建之后如何打印 trie 本身？

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']))

Answer 1

为了 return trie，您可能需要将 root 存储在安全的地方并且 return ：

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'])

如果我们打印出 trie，我们将看到如下内容：

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

只是为了确保正确构建 trie，我们可能想测试 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

这将return以下结果：

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

用字符串构建一个 trie 但 'str' object cannot be assigned error for some of the characters？

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

python

dictionary

trie