F. *_* P. 7 c++ algorithm optimization
我正在为一个大学项目实现一个基于文本的Scrabble版本.
我有一个包含大约400K字符串的向量(我的字典),并且,在每个回合的某个时刻,我将不得不检查字典中是否还有一个单词可以用玩家手中的碎片形成.我正在检查玩家是否有任何移动......如果没有,那么对于有问题的玩家来说,游戏就结束了......
我唯一的解决方案是逐个遍历字符串,并使用子程序,我必须检查所讨论的字符串是否可以从播放器的片段中形成.我将实现一个quickfail检查用户是否有任何元音,但它仍然是非常低效.
包含字典的文本文件已按字母顺序排序,因此矢量已排序.
有什么建议？
下面的评论中提出了一个问题:如何考虑如何考虑董事会已经写过的信件？
在没有给你任何特定代码的情况下(因为这毕竟是作业),一个通用的方法是从单词中的排序字母映射到实际的法律单词.
也就是说,如果你的字典文件只有单词ape,gum和mug,你的数据结构将如下所示:
aep -> ape
gmu -> gum, mug
然后,您可以简单地浏览玩家字母的排列,并快速识别该密钥是否存在于地图中.
您需要花费一些处理时间在启动时设置字典,但是您只需要执行一些快速查找,而不是每次都遍历整个列表.