通过前缀划分字符串的算法

Question

给定一个已排序的字符串列表 L 和一个正整数 N（N <= len（L）），如何通过长度为 N 的公共前缀有效地将 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”开头。请注意前缀长度不是固定的。该算法的关键要求是将具有共同前缀的字符串分组，使得组数尽可能接近但不超过N。

有了上述结果，我可以调用partition(L, 8, "13")来进一步筛选以“13”开头的子集：

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

这不是一道作业题。我需要为手头的项目编写这样一个算法。我可以使用“暴力”的方法来编写它，只是想知道是否有任何经典/著名的数据结构和/或算法能够实现证明时间/空间效率。

我考虑过 Trie 树，但担心它可能会消耗太多内存...

- xrfang

---

如果您能够指定空间/时间需求和数据规模，那将会很有帮助。在 len(L)~1e3 的规模下，无需编写任何额外的代码。 - leaf bebop

你的意思是第一句话中的“长度最多为N的公共前缀”吗？ - Petar Petrovic

@Petar Petrovic，“最多N”表示最多N个组，而不是前缀长度。 - xrfang

@leaf bebop 我先尝试暴力方法，然后研究这里提供的答案。 - xrfang

@xrfang 谢谢，但我不确定我理解了。所以目标是将字符串集合分成最多N组，每个组中的字符串必须具有前缀g_p。而且更多的组更好。这正确吗？ - Petar Petrovic

Answer 1

有几种算法可供选择，但前缀树是最好的选择。

前缀树（又称 trie 树）是一棵树，它的节点不存储键，而是存储部分键。例如，如果你有一个存储字符串的前缀树，那么每个节点都会是字符串中的一个字符。如果你有一个存储数组的前缀树，那么每个节点都会是该数组的一个元素。这些元素从根开始按顺序排列。因此，如果你在一个前缀树中存储单词“hello”，那么根节点将有一个子节点“h”，而“h”节点将有一个子节点“e”，“e”节点将有一个子节点“l”，依此类推。键的最深节点将具有某种布尔标志，指示它是某个键的终端节点。（这很重要，因为键的最后一个节点并不总是叶节点......考虑一个包含“dog”和“doggy”的前缀树）。前缀树适用于查找具有特定前缀的键。

- Remario

Answer 2

你需要使用基数树。 你可以阅读trie和基数树之间的区别。

- Pavel Nikolov