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

最近在一些采访中询问，“如何找到所有字符串的反向，如果存在超过百万字符串的列表中？在超过百万个字符串的列表中以相反顺序排列的字符串对？

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

方法1.存储所有的HashSet的琴弦，开始从第一个字符串遍历并检查反转形态存在的Hashset中，如果是的话，其他配对移动到下一个元素。

如果内存是约束，你能提出任何方法吗？

来源

2011-09-29 amit mathapati

在重 - 不清楚你是否想在同一个列表中找到所有与他人相反的字符串，或者给定一个字符串，在列表中找到与其相反的字符串。后者当然是一个简单的搜索问题，在你反转给定的字符串之后。 –

虽然我在这方面同意丹尼尔的观点，但考虑到MEMORY是一个约束条件，那根本就不重要。 –

@DanielRHicks我编辑了我的问题....他的意思是，对于列表中的所有字符串查找是否存在相反的... –

你可以使用Bloom Filter它会告诉你一个字符串是否已经存在于像结构这样的散列表中，但是每个存储桶只有0或1，因此使用的空间很小。

正好是1个000 000位== 125 KB

来源

2011-09-29 23:43:44 Serdalis

1.）这将需要更多的内存。 2）你不需要很长的字符串来获得很多长度相同的字符串。 –

你是对的，我会改变我的答案。 – Serdalis

答复已更改。 – Serdalis

如果允许的话，你可以就地排序琴弦所以当你查找的字符串的反向，你可以做一个二进制搜索。

来源

2011-09-29 23:50:02

首先我会使用独立于方向的散列来散列字符串。这可能是一个简单的字符总和，尽管从两端都会有更好的方案。为了“促成交易”，可以将字符串长度附加到散列值，否则将其并入散列中。

然后，当你把这些字符串分解成相同的散列组时，请做“长手”比较。

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

所以你只需要通过一组字符串来完成整个事情。

来源

2011-09-29 23:52:39

做一个方向独立的哈希值不会给你任何实际的好处，但肯定会增加碰撞率。 –

独立于方向的散列将“abc”和“cba”散列到同一个存储桶中。这大大减少了您必须尝试的组合数量。 –

我不明白。它为什么会减少任何东西？你在说什么组合？ –

随着“ 内存作为约束”，那么我甚至不会去一个HashSet（其中，据我所知也将删除原始列表复制的字符串），因为你将要使用的附加结构一个需要一些内存的HashSet。

~~排序，也不会改善内存使用情况。~~

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

的列表，包括“内存作为约束”迭代我会去2环。我认为C-like伪代码会更容易理解我的纯英文。

注：

问题中已提供的例子，它实际上不是一个列表而是一个数组，所以我会在结构上进行操作，就好像它是一个数组
问题不清楚如何配对这个“abc”，“def”，“cba”，“abc”。我会将第一个“abc”与“cba”配对，并且将“cba”与“第二个abc”配对（问题的意图还不清楚）
我假设我们无法修改原始列表

这里是至少内存消耗代码我能想到的：

// "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 usag e（实际上，根据问题无关），字符串将被颠倒的次数将为：（N *（N + 1））/ 2其中N是列表的长度

来源

2011-09-29 23:52:58

1,000,000,000,000次迭代，或多或少。（不包括实际的比较循环。） –

嗯，没有。在列表中迭代1次。这个解决方案的顺序是N.但正如我所说的那样，要求的人明确表示，没有必要尽快做到这一点，但只需要最少的内存。该列表已经存在，我只是增加了3个字节。您的解决方案需要多少个附加字节？ –

所以请解释一下如何通过列表中的一个通道来识别列表中的所有反转重复项。 –

您可以选择HashTable并使用桶来减少哈希冲突。我们现在需要为一个特定的查询字符串做的只是反转它，将它散列并在HashTable中查找，而不是从开始到结束遍历。

来源

2011-09-30 02:24:28

是的，这与我的方案基本相同，只有两倍的哈希值。 –

这是强制我认为：

我将创建一个哈希与

关键字符=

值=字符串列表与该字符开始

现在开始一个循环，你需要从第一个字符串开始。
扭转它
采取的第一个字符和搜索中的散列该键
然后在该值，它包含一个字符串列表，找到字符串在该列表中

来源

2011-09-30 05:16:51 Vijay

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

回答

相关问题