从10000个ASCII字符串中返回子集字符串

Question

我的大学快要结束了，所以我已经开始为了找工作而准备面试，当我在为面试做准备时，我遇到了这个面试问题。

1. 你有一组10000个 ASCII 字符串（从文件中加载）
2. 从标准输入输入一个字符串。
3. 编写伪代码，返回（到标准输出）与输入（2）具有相同不同字符集（无论顺序如何）的字符串子集 (1)。优化时间。
4. 假设需要反复调用此函数。初始化字符串数组一次并存储在内存中可以接受。请避免需要循环遍历所有10000个字符串的解决方案。

谁能给我提供一个通用的伪代码/算法之类的东西来解决这个问题？我正在想解决方案，但感觉很困难。我对 Java 最熟悉。

- AKIWEB

---

构建一个数据结构，可以将不同的字符映射到字符串列表（哈希表，访问为 O(1)）。一旦你拥有了这个数据结构，其余部分就很简单了。 - Vincent Savard

是的，问题说明我们需要避免需要循环遍历10000个字符串的解决方案。 - AKIWEB

我认为不可能在不循环10,000次的情况下知道一个集合是否包含在另一个集合中。@VincentSavard的解决方案是一种原始的方法，但实际上它似乎只是混淆了行动：它首先循环构建一个映射（增加了内存消耗），然后查看映射以计算结果，而不是循环并告诉字符串是否通过测试。我认为它将使用完全与dlev解决方案相同的CPU和内存，只是它有更好的外观 :) - Raffaele

我不确定“包含相同的不同字符”是什么意思。它是否指仅包含这些字符的字符串？重复的相同字符是否允许，还是只允许排列？ - jwd

@NeilCoffey请不要在帖子中添加“[homework]”标签，因为它已经正式弃用。 - NullUserException

Answer 1

这是一个O(1)算法！

初始化：

• 对于每个字符串，按字符排序并删除重复项 - 例如，“trees”变成“erst”
• 使用排序后的字符将已排序的单词加载到trie树中，在遍历的每个节点上添加对原始单词的引用以存储单词列表

搜索：

• 将输入字符串按与源字符串相同的方式进行排序
• 使用字符跟随源字符串trie，在末尾节点返回所有引用的单词

- Bohemian

---

值得注意的是，如果字符的可能值范围相当受限，则不一定需要对字符进行排序：您只需计算每个字符出现的次数即可。然后，您的键可以是包含这些计数的对象，或者仅是按顺序连接的计数的强哈希。这种问题部分是我在另一个评论中说“为了优化时间”，您确实需要更多关于输入数据通常是什么样子的信息。 - Neil Coffey

@NeilCoffey 我不同意。它需要被排序。请查看编辑后的答案——我改进（修复）了算法。现在它非常出色 :) - Bohemian

啊，好的，如果你使用前缀树而不是平面哈希映射，那么实际上是这样的。 （潜在地，前缀树的节点可以是字符计数，但此时我认为您可以使用我提到的带有平面映射的方法。） - Neil Coffey

我想看到这个编码和基准测试，因为在我看来，暴力部分只是从直接循环移动到了Trie.add()方法。我的观点是一旦Trie检测到了String的父节点，你已经有了解决方案，所以保留对象并遍历树是一种浪费。但也许我没有理解这个想法，所以我想知道是否有人可以编写这种方法。 - Raffaele

@Raffaele，实际上我想为了好玩而编写这个代码。不过我稍后会做 - 现在很忙。 - Bohemian

@Bohemian，这将非常有趣 :) 我已经在网上发布了一个初始的gist。希望你能发现它对实现你的算法有用。 - Raffaele

Answer 2

他们说要优化时间，所以我想我们可以尽情滥用空间。

在这种情况下，您可以对10000个字符串进行初始处理，并构建一个映射，将10000个字符串中出现的每个唯一字符映射到它们的索引（或其索引集）。这样，您可以向映射提问：“哪些集合包含字符'x'？”将此映射称为M>（当n是字符串数量，m是它们的最大长度时，顺序为O(nm)）

为了再次优化时间，您可以将stdin输入字符串缩小为唯一字符，并将它们放入队列Q中。 （顺序O(p)，其中p是输入字符串的长度）

开始一个新的不相交集，称为S。然后让S = Q.extractNextItem。

现在，您可以循环遍历其余的唯一字符，并找到包含所有这些字符的集合。

当（Q不为空）（循环O(p)）{

S = S intersect Q.extractNextItem（根据不相交集的实现方式，接近O(1)）

}

完成，返回 S。

总时间：O(mn + p + p*1) = O(mn + p)

（现在还很早，希望时间分析是正确的）

- dakotapearl

---

为了真正优化时间，您需要更多有关未提供的输入数据的信息。因此，我不会在这方面陷得太深——他们基本上想确保受访者能够探索算法选项，超越循环遍历所有字符串计算字符的“蛮力”选项。 - Neil Coffey

然而，他们要求优化时间，因此我认为提供时间分析会很有帮助。只是为了展示您理解您正在获得比最坏情况暴力破解更好的东西。 - dakotapearl

Answer 3

正如Bohemian所说，trie树绝对是正确的选择！

这听起来就像在手机上查找通讯录的方式。开始输入数字，然后根据数字表示以及该数字所代表的三个（如果使用国际字符，则实际上更多）字母之一过滤通讯录。

- Jay Pete