这里是一个词作为键的字典,
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 而不是后缀树这是此类数据结构的更节省空间的版本。
