在字典中求集合的最大深度

Question

我有一个字典，其中的键是一个字符串，而键的值是一组也包含键的字符串（单词链）。我找不到一个图的最大深度，它是字典中元素最多的集合，我试着打印出最大深度图。在

现在我的代码打印出来了：

{'DOG': [],
 'HIPPOPOTIMUS': [],
 'POT': ['SUPERPOT', 'HIPPOPOTIMUS'],
 'SUPERPOT': []}
1

其中1是我的最大字典深度。我原以为深度是两层，但“POT”的图形似乎只有一层

如何从字典中的一组键中找到最大值集？在

^{pr2}$

在测试字表.txt公司名称：

POT
SUPERPOT
HIPPOPOTIMUS
DOG

Answer 1

字典的“深度”自然是1加上词条的最大深度。您已将非字典的深度定义为零。由于您的顶级词典本身不包含任何字典，因此您的字典的深度显然是1。您的函数正确报告该值。在

但是，您编写的函数并不是期望您提供的数据格式。我们可以很容易地得到子串链的深度不止一个的输入。例如：

DOG
DOGMA
DOGMATIC
DOGHOUSE
POT

当前脚本的输出：

^{pr2}$

我想你应该为这个输入得到2，因为最长的子串链是DOG→DOGMA→DOGMATIC，它包含两个跃点。在

要在构建词典时获得字典的深度，需要计算每个单词的链长。这是1加上每个子串的最大链长，这给了我们以下两个函数：

def word_chain_length(d, w):
    if len(d[w]) == 0:
        return 0
    return 1 + max(word_chain_length(d, ww) for ww in d[w])

def dict_depth(d):
    print(max(word_chain_length(d, w) for w in d))

这里给出的word_chain_length函数不是特别有效。如果一个字符串是多个单词的子串，那么它可能会多次计算同一个链的长度。动态编程是缓解这种情况的一种简单方法，我将把它作为练习留给您。在

Answer 2

很抱歉，我的例子不是用python编写的，因为我的python已经生锈了，但是您应该知道这一点。在

假设这是一棵二叉树：
（用c++编写）

int depth(TreeNode* root){
  if(!root) return 0;
  return 1+max(depth(root->left), depth(root->right));
}

简单。现在让我们把这个扩展得更大一些，而不仅仅是左、右。
（果朗代码）

^{pr2}$

这样做的想法是，你只需查看每个字典，直到没有更多的字典可供下载，在你遍历的每个级别上添加1个。在