Skip to main content
 首页 » 编程设计

python之如何比较字典中的键并查看一个键是否包含另一个键

2024年12月31日12jillzhang

这里是一个词作为键的字典,

count_dict = { 
    'apple':2, 
    'pie': 1, 
    'pi':1, 
    'applepie':1 
} 

如果一个长词包含另一个短词,则将长词的计数加到短词上。这意味着结果是:

{ 
  'apple':3, 
  'pie': 2, 
  'pi':3, 
  'applepie':1 
} 

最简单的方法是使用一个简单的循环,

for i in list: 
    for j in list: 
        if len(i) < len(j) and i in j: 
            count_dict[i] += 1 

但是时间复杂度是O(n^2),太费时间了。 有什么办法可以降低复杂度来解决这个问题?

请您参考如下方法:

是的,您可以使用 Suffix tree 在 O(n) 时间内完成, 特别是看到 generalized suffix tree .您首先创建所有键的后缀树,之后您可以迭代每个键并在后缀树中搜索每个键(花费 O(len(key)) 时间)。

在你的树中找到 key 后,你可以找到你的 key 的所有子树,这些子树正是包含你的 key 的较长 key ,因此你可以获取每个子树并更新你的字典。

如果 m 是常量(比如你的键最多 100 个字符长)那么子树的数量也将是常量(最多一个高度为 100 的子树)所以整个事情花费 O(n) 时间。


您可以使用 suffix array 而不是后缀树这是此类数据结构的更节省空间的版本。