如何在Trie进行深度搜索？

Question

我编写了我的Trie解决方案，其中使用了defaultdict。任务是查找所有带有前缀的单词。格式必须类似于{of:of，offten，攻势}

在这里，我的Trie课：

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