C++ - 如何有效地找出 vector 中的任何字符串是否可以从一组字母中组装出来

Question

我正在为一个大学项目实现基于文本的拼字游戏。

我有一个包含大约 40 万个字符串的 vector (我的字典)，并且在每个回合的某个时刻，我将不得不检查字典中是否还有一个可以用玩家手中的棋子。我正在检查玩家是否还有任何移动...如果没有，则有问题的玩家游戏结束...

对此，我唯一的解决方案是逐一遍历字符串，并使用子例程检查所讨论的字符串是否可以由玩家的棋子组成。我将实现快速失败检查用户是否有任何元音字母，但它仍然非常低效。

包含字典的文本文件已经按字母顺序排列，因此 vector 已排序。

有什么建议吗？

---

下面的评论中提出了一个问题:关于如何考虑板上已经存在的字母有什么建议吗？

Answer 1

在不给你任何具体代码的情况下(因为这毕竟是家庭作业)，一种通用的考虑方法是将单词中排序的字母映射到实际的合法单词。

也就是说，如果您的字典文件只有单词 ape、gum 和 mug，您的数据结构将如下所示:

aep -> ape
gmu -> gum, mug

然后您可以简单地遍历玩家字母的排列，并快速确定该键是否存在于 map 中。

您需要在启动时花费一些处理时间来设置字典，但随后您只需执行几次快速查找，而不是每次都遍历整个列表。