string - 按前缀划分字符串的算法

Question

给定一个字符串列表 L(已排序)和一个正整数 N(N <= len(L))，如何通过长度为 N 的公共(public)前缀有效地将 L 分成不超过 N 个组？

例子:定义数据结构和函数如下:

type PrefixGroup struct {
    Prefix string 
    Count  int
}
func partition(L []string, N int, prefix string) []PrefixGroup

当调用时，列表 L 可能包含数千个字符串

partition(L, 8, "")

输出可能是:

[
    {"Prefix":"13", "Count":1000},
    {"Prefix":"180": "Count": 10},
    {"Prefix":"X": "Count": 2},
    ... ...
]

这意味着在L中，有1000个以“13”开头的字符串，10个以“180”开头的字符串和2个以“X”开头的字符串。请注意前缀的长度不是固定的。该算法的关键要求是对具有公共(public)前缀的字符串进行划分，使分组数尽可能接近但不超过N。

有了上面的结果，我就可以调用 partition(L, 8, "13") 进一步挖掘以“13”开头的 L 子集:

[
    {"Prefix":"131", "Count": 50},
    {"Prefix":"135": "Count": 100},
    {"Prefix":"136": "Count": 500},
    ... ...
]

这不是家庭作业问题。我需要为手头的项目编写这样的算法。我可以“蛮力”地写它，只是想知道是否有任何经典/众所周知的数据结构和/或算法来实现经过验证的时间/空间效率。

我考虑过trie，但不知道它是否会消耗太多内存...

Answer 1

您需要使用 Radix trie .您可以阅读有关 the difference between a trie and a Radix trie 的信息.