3

这是一个家庭作业，所以我不想要确切的代码，但如果有任何想法可以帮助我指出正确的方向，我将不胜感激。

任务是编写一个解谜程序。我感觉递归部分已经下降，但我需要一些关于如何将当前字符序列与字典进行比较的见解。

我需要将字典存储在集合或排序列表中。我一直在尝试一种使用集合来实现这一点的方法。为了使程序运行得更快并且不走死胡同，我需要检查当前字符序列是否作为集合（字典）中任何内容的前缀存在。

我发现 set.find() 操作仅在字符串完全匹配时才返回 true。在实验室要求中，教授提到：

“如果字典存储在一个集合中，许多数据结构库都提供了一种方法来查找集合中与您正在搜索的字符串最接近的字符串。这样的操作可用于快速查找具有给定前缀的单词。”

我今天一直在寻找教授所描述的内容。我找到了很多关于尝试的信息，但由于我需要使用列表或集合，我认为这不会起作用。

我也尝试过查找自动完成功能的算法，但我发现的那些对于我在这里想要完成的任务来说似乎非常复杂。

我还考虑使用 strncmp() 将当前序列与字典集中的一个词进行比较，但同样，我不知道在这种情况下它究竟会如何发挥作用，如果有的话。

是否值得继续研究这将如何在集合中工作，或者我应该尝试使用排序列表来存储我的字典？

谢谢

4

2 回答 2

4

正如@Raymond Hettinger 在他的回答中提到的那样，特里在这里会非常有用。但是，如果您不喜欢编写 trie 或者更喜欢使用现成的组件，您可以使用单词按字母顺序排列的可爱属性来检查给定前缀是否存在的 O(log n) 时间。这个想法如下 - 例如，假设您正在检查前缀“thr”。如果您注意到，以前缀“thr”开头的每个单词都必须夹在字符串“thr”和“ths”之间。例如，thr ≤ through < ths，以及 thr ≤throat < ths。如果您将单词存储在一个巨大的排序数组中，您可以使用二进制搜索的修改版本来按字母顺序查找第一个单词，至少是您选择的前缀，并按字母顺序查找第一个单词，至少是下一个前缀（通过取前缀的最后一个字母并将其递增）。如果它们是同一个词，那么它们之间没有任何东西，前缀也不存在。如果它们不是，那么它们之间存在某些东西，并且前缀会这样做。

由于您使用的是 C++，因此您可能会使用 astd::vector和std::lower_bound算法。您也可以将所有单词放入 astd::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（有向无环字图）的数据结构，它类似于 trie，但使用的内存要少得多；在斯坦福的 CS 入门课程（其中 Boggle 是一项作业）中，实际上为学生提供了一个包含该语言中所有单词的 DAWG。还有另一种称为三元搜索树的数据结构，它位于二叉搜索树和特里树之间，如果您想研究一下，它可能在这里有用。

希望这可以帮助！

于 2012-01-29T03:26:27.680 回答
3

trie是解决此问题的首选数据结构。

如果您仅限于集合和字典，我会选择一个将前缀映射到可能匹配数组的字典：

asp -> aspberger aspire
bal -> balloon balance bale baleen ...
于 2012-01-29T03:02:41.483 回答