Return 个与 Trie 中的前缀匹配的字符串

Question

我设法构建了一个 Trie，现在我想 return 与 Trie 中的前缀匹配的字符串，但我在编写搜索函数时遇到问题。

例如，如果我有前缀 "aa"，我想将字符串 "aa" 和 "aac" 作为输出。

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.end = False
        self.value = ""

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

    def add_word(self, key):
        word_length = len(key)
        current = self.root
        for i in range(word_length):
            position = self.ord_char(key[i])

            if current.children[position] is None:
                current.children[position] = Node()
            current = current.children[position]
            current.value = key[i]
        current.end = True

    def ord_char(self,key):
        ord_rep = ord(key) - ord('a')
        return ord_rep

    def prefix_search(self, prefix):
        lst = []
        current = self.root
        prefix_length = len(prefix)
        for c in range(prefix_length):
            c_position = self.ord_char(prefix[c])
            current = current.children[c_position]
            lst.append(current.value)
        #doesnt seem like I'm doing it right

if __name__ == "__main__":
    trie = Trie()
    trie.add_word("aa")
    trie.add_word("aac")
    trie.add_word("b")
    trie.prefix_search("aa")

我正在考虑通过搜索功能将字母组合在一起形成最终字符串，但我想不出更好的方法。

Answer 1

那 .startswith() 呢，在我看来这是实现搜索的简单方法。

Answer 2

目前的 lst 值只是前缀，拆分成单独的字母，但现在您需要处理在 children 属性中找到的每个不是 [=14= 的节点], 以查找 end 设置为 True 的所有节点。每次找到这样的节点，你就有了一个完整的单词。任何节点又可以有多个 child 个节点，分支出更多的词来输出。

您可以使用堆栈来跟踪构建列表所需处理的所有节点，以及它们到目前为止的前缀。使用该节点的前缀将 child 个节点添加到堆栈中，并逐个处理这些节点（在执行此操作时将更多 child 个节点添加到堆栈中）。

请注意，首先，您不需要构建前缀字符列表，您已经将该前缀作为变量。要到达起点，只需遍历前缀本身会更简单：

def prefix_search(self, prefix):
    current = self.root
    # get to the starting point
    for c in prefix:
        current = current.children[self.ord_char(c)]
        if current is None:
            # prefix doesn't exist, abort with an empty list
            return []

    found = []
    stack = [(current, prefix)]
    while stack:
        current, prefix = stack.pop()

        if current.end:
            # this is a complete word, named by prefix
            found.append(prefix)

        # add the children to the stack, each with their letter added to the
        # prefix value.
        for child in current.children:
            if child is None:
                continue
            stack.append((child, prefix + child.value))

    return found

对于您给定的样本特里树和前缀，堆栈从 'aa' 处的节点开始。第一个 while stack: 迭代从堆栈中删除该节点，因为此节点已将 end 设置为 true，所以 'aa' 被添加到 found。该节点只有一个非 None child 节点，对于 c，因此该节点被添加到具有 'aac'.

的堆栈中

然后while循环重复，发现栈上有一个元素，看到end被设置所以'aac'被添加到found，没有更多child节点所在。堆栈保持为空，while 循环结束。

演示：

>>> trie = Trie()
>>> trie.add_word("aa")
>>> trie.add_word("aac")
>>> trie.add_word("b")
>>> trie.prefix_search("aa")
['aa', 'aac']
>>> trie.prefix_search("b")
['b']
>>> trie.add_word('abracadabra')
>>> trie.add_word('abbreviation')
>>> trie.add_word('abbreviated')
>>> trie.add_word('abbrasive')
>>> trie.prefix_search("ab")
['abracadabra', 'abbreviation', 'abbreviated', 'abbrasive']
>>> trie.prefix_search("abr")
['abracadabra']
>>> trie.prefix_search("abb")
['abbreviation', 'abbreviated', 'abbrasive']
>>> trie.prefix_search("abbra")
['abbrasive']

Return 个与 Trie 中的前缀匹配的字符串

Return strings that matches the prefix in a Trie

python

trie