python - Trie 字典中的前缀搜索

Question

我有一个示例字典

    {  
   'A':{  
      'P':{  
         'P':{  
            'L':{  
               'I':{  
                  'E':{  
                     'S':{  
                        '*':True
                     }
                  }
               },
               'E':{  
                  'S':{  
                     '*':True
                  },
                  '*':True
               }
            }
         },
         'E':{  
            '*':True
         }
      }
   }
}

这里的{*:True}表示词尾。我需要找到我可以从字典中以前缀开头的所有可能的单词。例如，我可以从上面的字典中生成带有各种前缀的单词如下。

1. 'AP' -> "APPLE", "APPLES""APE", "APPLIES"

2. 'APP' -> "APPLE", "APPLES", "APPLIES"

3. '苹果' -> "苹果", "苹果"

我基本上是在尝试使用字典实现 Trie 数据结构并执行前缀搜索。我想我应该实现一些递归算法来找到所有可能的结果。我无法弄清楚如何实现它。

Answer 1

我很好奇并想出了这个递归变体:

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