C Boggle求解器：在集合中查找前缀
|
这是一个家庭作业,所以我不想要确切的代码,但会欣赏任何可以帮助我指出正确方向的想法.
任务是编写一个boggle解决程序.我觉得我已经得到了递归部分,但是我需要一些有关如何将当前字符序列与字典进行比较的见解. 我需要将字典存储在集合或排序列表中.我一直在尝试使用set来实现它.为了使程序运行得更快而不遵循死端路径,我需要检查并查看当前字符序列是否作为集合(字典)中任何内容的前缀存在. 我发现如果字符串完全匹配,set.find()操作只返回true.在实验室要求中,教授提到： “如果字典存储在Set中,许多数据结构库提供了一种方法来查找Set中最接近您正在搜索的字符串的字符串.这样的操作可用于快速查找具有给定前缀的单词“. 我今天一直在寻找教授所描述的内容.我已经找到了很多关于尝试的信息,但由于我需要使用列表或集合,我认为这不会起作用. 我也试过查找自动完成函数的算法,但是我发现的那些算法对于我在这里要完成的事情看起来非常复杂. 我也在考虑使用strncmp()将当前序列与字典集中的单词进行比较,但同样,我不知道在这种情况下它究竟会起作用,如果有的话. 是否值得继续调查它如何在一个集合中工作或者我应该尝试使用排序列表来存储我的字典？ 谢谢 解决方法
正如@Raymond Hettinger在他的回答中提到的,trie在这里非常有用.但是,如果您对编写trie感到不舒服或者更喜欢使用现成的组件,则可以使用字母顺序排序字的可爱属性来检查O(log n)时间是否存在给定前缀.这个想法如下 – 假设您正在检查前缀“thr”.如果你注意,每个以前缀“thr”开头的单词都必须夹在字符串“thr”和“ths”之间.例如,thr≤to< ths和thr≤throat<部份.如果您将单词存储在一个巨大的排序数组中,您可以使用二进制搜索的修改版本按字母顺序查找至少所选前缀的第一个单词,并按字母顺序查找至少下一个前缀的第一个单词(由最后一个前缀形成)前缀的字母并递增它).如果这些是相同的单词,则它们之间没有任何内容,前缀不存在.如果他们不是,那么他们之间会有一些东西和前缀. 由于您使用的是C,因此可以使用std :: vector和std :: lower_bound算法.您还可以将所有单词都放入std :: set并使用set的lower_bound版本.例如：
std::set<std::string> dictionary;
std::string prefix = /* ... */
/* Get the next prefix. */
std::string nextPrefix = prefix;
nextPrefix[nextPrefix.length() - 1]++;
/* Check whether there is something with the prefix. */
if (dictionary.lower_bound(prefix) != dictionary.lower_bound(nextPrefix)) {
/* ... something has that prefix ... */
} else {
/* ... no word has that prefix ... */
}
也就是说,这里的trie可能是一个更好的结构.如果您感兴趣,还有另一个名为DAWG (Directed Acyclic Word Graph)的数据结构类似于trie但使用的内存要少得多;在斯坦福大学的入门CS课程(其中Boggle是一项任务)中,学生实际上被提供了一个包含该语言所有单词的DAWG.还有另一个名为ternary search tree的数据结构,它位于二进制搜索树和trie之间,如果您想查看它,可能在这里很有用. 希望这可以帮助！ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |