1

可以使一组字符串唯一的最少字符数是多少（从第一个字符开始）。

例如，一组字符串：

{
    'january',
    'february',
    'march',
    'april',
    'may',
    'june',
    'july'
}

现在，我们不能只使用第一个字符，因为 'j' 既在 'june' 中，又在 'july' 中（另外，'m' 在 'march' 和 'may' 中）。我们也不能使用前 2 个字符，因为 'ma' 既在 'march' 又在 'may' 中。

但是，我们可以使用前 3 个字符！

返回这个数字的最佳算法是什么（除了明显的蛮力）？

4

2 回答 2

2

您可以优化的第一件事是对所需前缀的大小进行二进制搜索。该函数是单调的 - 如果给定数量的字符 n 就足够了，那么任何大于 n 的值也可以。

其次 - 您可以计算每个字符串的滚动哈希，以便您可以在恒定时间内获得每个字符串的给定前缀的哈希码。因此，您将不得不验证数字（哈希码）的唯一性，而不是字符串，这当然更快。我建议像rabin-karp那样滚动哈希。

于 2013-04-25T07:12:54.193 回答
2

您可以对数据进行排序并比较相邻条目之间不同的第一个字符的索引。这具有 O(N log N) 的复杂性或排序的复杂性。

如果可以将索引计算合并到 compare 函数中，则可以得到一个副作用：结果应该是 compare 函数遇到的最大索引。

正如 Steve Jessop 评论的那样，问题可能没有解决方案。确实可以首先计算条目的最小长度。如果可以自由实现比较函数，另一种选择是在比较函数遇到字符串结尾时返回 -1。

int global_max = 0;
int compare(const char *a, const char *b) {
    int c=0;
    int result;  // result of comparison -- set as zero if an error has occured
    if (global_max < 0) return 0;
    do {
       if (*a==0 || *b==0) { global_max = -1; return 0; }
       c++;
    } while ((result = (*a++ - *b++)) == 0);
    if (c>global_max) global_max = c;
    return result;
}
于 2013-04-25T07:16:04.820 回答