缩短已排序列表

Question

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

例如：

abcd01c, abcd02c, abcd04c, abcd05, z1x

应该变成

abcd0[1-4]c,abcd05,z1x

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

- James Raitsev

---

这些缩写名称是要存储为字符串吗？还是您使用abcd0[1-4]c代替特殊的包装对象？ - Eric

你事先知道这些模式吗？（例如abcdNNc，abcdNN等） - Brian Roach

@Eric 我认为这并不重要。在这种情况下，我会寻找最简单的实现方式。它们可以是字符串，也可以是某个理解前缀/范围/后缀的对象的一部分。 - James Raitsev

@Brian 我没有。我保证拥有的只是一个已排序的字符串列表，我应该尝试缩短它。假设前缀和后缀相同，我会依赖于范围格式为[low-high]。 - James Raitsev

你能给我们提供一组折叠名称的规则吗？方括号范围只能用来代替单个字符吗？范围是否定义了一系列ASCII代码？ - Eric

Answer 1

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

将字符串存储为：

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

这个数字是从前一个字符串中取出的字符数。这是类似电话簿等需要存储许多相似字符串的字典的常见实现方式。 Trie 是一种类似的结构，正如 Brian Roach 在评论中指出的那样。

- Daniel

---

通常情况下，您可以使用Trie来实现这个功能...我认为您可以在此处使用它来存储所有内容，只需要一个自定义遍历函数以按所需格式获取数据即可。 - Brian Roach

Answer 2

我认为动态规划可以帮助解决问题。可以计算给定数组所有第一个元素的集合的最短长度，例如 {1}，{1,2}，{1,2,3}... 这些数字是连续计算的，因此需要使用先前的数字来计算当前数字。如果我们想要计算 A[i]，并且已知 A[j]（其中 j < i），并且从 j+1 到 i 的给定数组中的数字可以被压缩，则 A[i] 等于 A[j] + 压缩数据的长度。

更新

如果范围设置为多个符号，我几乎不理解如何进行压缩。因此，在这里提供了一种简单的实现方式，适用于一个符号的情况。

int prevIdx = -1;
int count = 0;
for (int i = 1; i < list.Length; i++) {
    bool ok = true;
    if (list[i].Length == list[i - 1].Length) {
        int count = 0;
        for (int j = 0; j < list[i].Length; j++)
            if (list[i][j] != list[i - 1][j])
                curIdx = j;
                count++;
            }
        if (count > 1)
            ok = false;
    }
    else
        ok = false;
    if (ok) {
        if (prevIdx == curIdx) {
            count++;
        }
        else {
            prevIdx = curIdx;
            if (count > 1)
                answer.Add(list[i - 1].SubString(0, prevIdx - 1) + 
                    '[' + count.ToString() + ']' + list[i - 1].SubString(prevIdx + 1, list[i - 1].Length);
            else
                answer.Add(list[i - 1]);
            count = 0;
        }
    }
    else {
        if (count > 1)
            answer.Add(list[i - 1].SubString(0, prevIdx - 1) + 
                '[' + count.ToString() + ']' + list[i - 1].SubString(prevIdx + 1, list[i - 1].Length);
        else
            answer.Add(list[i - 1]);
        prevIdx = -1;
    }
}
if (count > 1)
    answer.Add(list[List.Length - 1].SubString(0, prevIdx - 1) + 
        '[' + count.ToString() + ']' + list[i - 1].SubString(prevIdx + 1, list[List.Length - 1].Length);
else
    answer.Add(list[list.Length - 1]);

- fdermishin

---

有没有可能提供一个例子？ - James Raitsev

Answer 3

我对您的实际需求有些摸不着头脑，但是一种解决方法是使用自定义Trie（维基百科条目）。

当您到达键中下一个字符不是字母字符的点时，您将知道您有一个前缀。在Trie中的该节点内，您可以再次拥有另一个映射（不指向其他Trie节点），其由后缀键入并包含每个范围。

然而，您仍然面临特定数据规则的问题。如果您的键为abcd01c，那么前缀是abcd还是abcd0？

- Brian Roach