java - 缩短排序列表

Question

假设您有一个包含服务器名称的排序列表。您希望尽可能紧密地折叠它们。

例子:

abcd01c, abcd02c, abcd04c, abcd05, z1x

应该变成

abcd0[1-4]c,abcd05,z1x

处理此类问题的最简单算法是什么？

Answer 1

我会将所有字符串存储在前缀映射中，这使得判断字符串是否存在变得非常容易，并且还允许快速迭代字符串的子集。

将字符串存储为:

(0)abcd01c
(5)     2c, 
(5)     4c, 
(4)    05, 
(0)z1x

数字是必须从前一个字符串中取出的字符数。这是电话簿等字典的常见实现，您必须在其中存储许多相似的字符串。

A Trie是一个类似的结构，如Brian Roach在评论中注意到。