java - 用另一组字母检查单词中字母的算法和数据结构

Question

我有一本包含 200,000 个单词的字典和一组字母。我需要一个算法来检查一个单词的所有字母是否都在这组字母中。一个个查单词很慢。因为要处理大量的单词，所以我需要一个数据结构来执行此操作。有任何想法吗？谢谢！

例如：我有一组字母 {b,g,e,f,t,u,i,t,g,n,c,m,m,w,c,s}，我想检查单词“big ”和“buff”。“big”的所有字母都是原始集合的子集，然后“big”是我想要的，而“buff”不是我想要的，因为原始集合中只有一个“f”。这就是我想做的。

Answer 1

这是为了像Scrabble或Boggle这样的东西，对吧？好吧，您所做的是通过对每个单词中的字母进行排序来预先生成您的字典。所以，word变成dorw。然后你把所有这些都塞进一个 Trie 数据结构中。因此，在您的 Trie 中，序列dorw将指向 value word。

[注意，因为我们对单词进行了排序，它们失去了唯一性，所以一个排序的单词可以指向多个不同的单词。 即您的 Trie 需要在其数据节点上存储一个列表或数组]

如果您需要稍后快速加载它而无需所有排序步骤，您可以保存此结构。

然后你要做的是获取你输入的字母，然后你也对它们进行排序。然后你开始递归遍历你的 Trie。如果当前字母与 Trie 中的现有路径匹配，则跟随它。因为您可以有未使用的字母，所以您也允许删除当前字母。

就这么简单。每当您在 Trie 中遇到一个具有值的节点时，您就可以从您用来到达那里的字母中得出一个单词。您只需在找到这些单词时将它们添加到列表中，当递归完成时，您已经找到了所有可能的单词。

如果您的输入中有重复的字母，您可能需要额外的逻辑来防止给出相同单词的多个实例（除非您愿意）。可以在“省略”一个字母（您只需跳过所有重复的字母）到下一个字母的步骤中调用该逻辑。

---

[编辑] 你似乎想做相反的事情。我上面的解决方案找到了可以由一组字母组成的所有可能的单词。但是你想测试一个特定的单词，看看它是否被允许，给定你拥有的一组字母。

这很简单。

将可用字母存储为直方图。也就是说，对于每个字母，您存储您拥有的数字。然后，您遍历测试词中的每个字母，边走边构建一个新的直方图。一旦您的直方图存储桶中的一个超过可用字母中的值，就无法生成该单词。如果你一路走到最后，你就可以成功地造字。

Answer 2

您可以使用数组来标记字母集。数组中的每个元素代表一个字母。要将字母转换为元素位置，只需减去'a'或'A'的ASCII码。然后第一个元素代表“a”，然后第二个元素代表“b”，依此类推。然后 27 号是“A”。元素值代表出现次数。例如，数组 {2, 0, 1, 0, ...} 代表 like {a, c, a}。伪代码可以是：

    对于每个单词
        将数组复制到一个新数组
        对于单词中的每个字母
            获取字母的元素位置： position = letter - 'a'
            将新数组中的元素值减一：new_array[position]--
            如果值为负，则返回未找到： if array[position] < 0 {return not found;}

Answer 3

对集合进行排序，然后对每个单词进行排序并执行类似“合并”的操作