我有一个示例字典
{
'A':{
'P':{
'P':{
'L':{
'I':{
'E':{
'S':{
'*':True
}
}
},
'E':{
'S':{
'*':True
},
'*':True
}
}
},
'E':{
'*':True
}
}
}
}
这里的{*:True}
表示词尾。我需要找到我可以从字典中以前缀开头的所有可能的单词。例如,我可以从上面的字典中生成带有各种前缀的单词如下。
'AP' -> "APPLE", "APPLES""APE", "APPLIES"
'APP' -> "APPLE", "APPLES", "APPLIES"
'苹果' -> "苹果", "苹果"
我基本上是在尝试使用字典实现 Trie 数据结构并执行前缀搜索。我想我应该实现一些递归算法来找到所有可能的结果。我无法弄清楚如何实现它。
最佳答案
我很好奇并想出了这个递归变体:
tree = {
"A": {
"P": {
"P": {
"L": {
"I": {"E": {"S": {"*": True}}},
"E": {"S": {"*": True}, "*": True},
}
},
"E": {"*": True},
}
}
}
def descend(node, prefix=""):
if prefix and prefix[-1] == "*":
print(prefix[:-1])
return
for letter, node in node.items():
descend(node, prefix + letter)
descend(tree)
它打印:
APPLIES
APPLES
APPLE
APE
关于python - Trie 字典中的前缀搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57692519/