Как сделать глубинный поиск в Tr ie?

Question

Я написал свое решение Tr ie, где я использовал defaultdict . Задача найти все слова с префиксом. Формат должен быть как {of: [of, offten, оскорбительный]}

Здесь мой Tr ie класс:

from collections import defaultdict

def _trie():
    return defaultdict(_trie)

TERMINAL = None

class Trie(object):
    def __init__(self):
        self.trie = _trie()

    def addWord(self, word):
        trie = self.trie
        for letter in word:
            trie = trie[letter]
        trie[TERMINAL]


    def search(self, word, trie=None):
        if trie is None:
            trie = self.trie
        for i, letter in enumerate(word):
            if letter in trie:
                trie = trie[letter]
            else:
                return False
        return trie

Здесь Пример:

Trie = Trie()
Trie.addWord('of')
Trie.addWord('often')
Trie.addWord('offensive')


string = 'of'
s = dict(Trie.search(string))

Они дают результат:

Answer 1

Здесь я делаю поиск глубины

from collections import defaultdict
class TrieNode:
def __init__(self):
    self.child = defaultdict(TrieNode)
    self.is_word = False
    self.words = ""

class Trie:
def __init__(self):
    self.root = TrieNode()

def insert(self, word):
    cur = self.root
    for i in range(len(word)):
        cur = cur.child[word[i]]
        cur.words = word[:i+1]
    cur.is_word = True

def search(self, word):
    cur = self.root
    for char in word:
        cur = cur.child.get(char)
        if not cur:
            return []
    stack = [cur]
    res = []
    while stack:
        node = stack.pop()
        if node.is_word:
            res.append(node.words)
        for key, val in node.child.items():
            stack.append(val)
    return sorted(res)

Trie = Trie()
Trie.insert('of')
Trie.insert('often')
Trie.insert('offensive')
Trie.insert('offensive2')

Trie.search('o')

# ['of', 'offensive', 'offensive2', 'often']