在超过一百万个字符串的列表中按相反顺序排列字符串对？

Question

最近在一些采访中被问到“如果存在于超过一百万个字符串的列表中，如何找到所有字符串的反转？

对于例如 str[1] =“abc”，我需要准确地检查“cba”，没有字谜。

方法1. 将所有字符串存储在哈希集中，从第一个字符串开始遍历，如果存在，则将其配对移动到下一个元素，

如果内存是限制，您能建议任何方法吗？

Answer 1

如果允许，您可以对字符串进行就地排序，这样当您查找字符串的反向时，您可以进行二分搜索。

Answer 2

您可以使用 Bloom Filter 它会告诉您字符串是否已存在于类似哈希表的结构中，但每个桶只有 0 或 1，因此使用的空间非常少。

恰好 1 000 000 位 == 125 KB

Answer 3

您可以选择HashTable并使用桶来减少哈希冲突。我们现在需要对特定的查询字符串做的只是将其反转、散列并在 HashTable 中查找，而不是从头到尾遍历。

Answer 4

这只是我的观点：

创建一个哈希

我将使用key=character

value=以该字符开头的字符串列表< /em>

• 现在开始一个循环，您需要从第一个字符串开始。
• 反转它
• 取第一个字符并在散列中搜索该键，
• 然后在该值中搜索，它包含字符串列表并在该列表中找到该字符串

Answer 5

<罢工>
使用“内存作为约束”，那么我什至不会选择 HashSet（据我所知，它也会删除原始列表中的重复字符串），因为您将使用 a 的附加结构HashSet 需要一些内存。

排序，也不会提高内存使用率。

我将使用原始列表（已经存在，因此不会使用额外的内存）+ 3 字节整数变量来迭代列表。 3 个字节可以迭代 2^24 = 16777216 个字符串的列表

如果“内存作为约束”，我会进行 2 个 for 循环。我认为类似 C 的伪代码会比我的简单英语更容易理解。

注意：

1. 从问题中提供的示例来看，它实际上不是一个列表，而是一个数组，所以我将像它是一个数组一样对该结构进行操作
2. 问题不清楚如何配对这个“abc”，“def” 、“cba”、“abc”。我将把第一个“abc”与“cba”配对，并将“cba”与“第二个“abc”配对（问题中的意图不清楚）
3. 我认为我们无法修改原始列表

这是最少的记忆-我能想到的消耗代码：

// "list" holds the original list (array)
for (int i = 0; i < length(list) - 1; i++) {
    for (int j = i + 1; j < length(list); j++) {
        if (list[i] == reverse(list[j])) {
            print(list[i] + " reversed is " list[j])
        }
    }
}

关于内存使用情况，这个解决方案将采用2个整数变量（通常每个4字节）+原始列表，我认为我们无法摆脱

关于CPU使用情况（实际上，基于不相关 。的问题），字符串反转的次数将为：(N*(N+1))/2，其中 N 是列表的长度

Answer 6

首先，我将使用与方向无关的散列对字符串进行散列。这可能是一个简单的字符总和，尽管肯定有更好的方案可以从两端进行散列。为了“使交易更顺利”，人们可以将字符串长度附加到哈希值中，或者以其他方式将其合并到哈希中。

然后，当您将字符串分成相同的哈希组时，进行“长手”比较。

请注意，使用此方案或仅向前或向后使用方向相关哈希的方案，要做的事情是不要立即将字符串插入哈希集中，而是检查它（如果需要，使用反向哈希）首先，如果你得到一个匹配（并且随后的长比较为真），则删除已经散列的字符串并将两者配对。第二个字符串永远不会进入集合，并且，如果所有字符串最多都匹配，则哈希集中只会有 500,000 个条目，并且，如果字符串是随机的，则可能接近 250,000 个（我没有坐过）来计算概率）。

因此，您只需要遍历一组字符串即可完成整个操作。