我正在为一个大学项目实现基于文本的拼字游戏。
我有一个包含大约 40 万个字符串的 vector (我的字典),并且在每个回合的某个时刻,我将不得不检查字典中是否还有一个可以用玩家手中的棋子。我正在检查玩家是否还有任何移动...如果没有,则有问题的玩家游戏结束...
对此,我唯一的解决方案是逐一遍历字符串,并使用子例程检查所讨论的字符串是否可以由玩家的棋子组成。我将实现快速失败检查用户是否有任何元音字母,但它仍然非常低效。
包含字典的文本文件已经按字母顺序排列,因此 vector 已排序。
有什么建议吗?
下面的评论中提出了一个问题:关于如何考虑板上已经存在的字母有什么建议吗?
最佳答案
在不给你任何具体代码的情况下(因为这毕竟是家庭作业),一种通用的考虑方法是将单词中排序的字母映射到实际的合法单词。
也就是说,如果您的字典文件只有单词 ape
、gum
和 mug
,您的数据结构将如下所示:
aep -> ape
gmu -> gum, mug
然后您可以简单地遍历玩家字母的排列,并快速确定该键是否存在于 map 中。
您需要在启动时花费一些处理时间来设置字典,但随后您只需执行几次快速查找,而不是每次都遍历整个列表。
关于C++ - 如何有效地找出 vector 中的任何字符串是否可以从一组字母中组装出来,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2835910/