65.9K
CodeProject 正在变化。 阅读更多。
Home

打乱单词求解工具

greba
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.42/5 (16投票s)

2003年11月25日

4分钟阅读

viewsIcon

178729

downloadIcon

2777

该程序可以从一个打乱的单词中找到字典里所有可以组成的单词。

引言

该程序可以从一个打乱的单词中找到字典里所有可以组成的单词。

背景

我从来不擅长解决 Jumble 题，主要是因为我的词汇量里不包含他们喜欢使用的一些生僻词。Jumble 是一种字谜游戏，可以在报纸和一些网站（如 jumble.com）上找到。一个基本的 Jumble 问题就是一堆字母，重新排列后可以组成一个单词。问题的答案是原始打乱单词的变位词，例如：lbujme -> jumble。这个程序会接收这堆字母，然后列出所有（在字典中找到的）可以由这些字母组成的单词。

使用代码

要在您自己的应用程序中使用该代码，只需将 trie.cpp 和 trie.h 包含到您的项目源代码中，并在您想使用该类时 #include "trie.h"。

一个非常简单的 CTrie 类使用示例

//Create the List
CTrie* List = new CTrie();

//Add a word to the List
List->AddWord("jumble");

//Get a vector of words from the List
vector<CHAR*>* all = List->GiveWords("lbujme");

//Output the results
if (all && !all->empty())
{
    vector<CHAR*>::const_iterator vai;
    int cnt = 0;
    for (vai = all->begin(); vai != all->end(); vai++, cnt++)
        cout << cnt + 1 << " " << *vai << endl;
}
else
    cout << "none" << endl;

算法概述

我的算法基于一个原理：一个单词如果能由打乱的单词组成，那么这个单词中每个字母的出现次数必须与打乱的单词中该字母的出现次数相同。换句话说，lbujme 包含：1 个 B，1 个 E，1 个 J，1 个 M，1 个 L，1 个 U，而 jumble 包含：1 个 B，1 个 E，1 个 J，1 个 M，1 个 L，1 个 U。它们相同，因此你可以用 lbujme 组成 jumble。我的算法使用的数据结构是二叉树。树从根节点开始，根节点包含一个列表中所有字母“a”出现次数为零的单词。根节点然后可以有左右指针。左指针指向字母“a”和字母“b”出现次数都为零的节点。右指针指向字母“a”出现一次的节点。这可以泛化为：在树中向左移动意味着移动到下一个字母。向右移动意味着增加当前字母的出现次数。

CodeProject 之前的历史

我第一次编写 Jumble 解决程序大约是在五年前。查找六个字母的打乱单词的所有可能单词大约需要五分钟。我估计八个字母可能需要半天。我从未弄清楚具体需要多长时间。此外，原始程序是用 Turbo Pascal 编写的；我可以说是算法慢的原因，但必须归咎于程序员。

原始算法是将字母的所有可能组合（包括重复字母）排列出来，然后检查它是否是一个单词。对于六个字母的单词，这会产生 6^6 = 46656 个单词需要检查。不算太糟，但我每次都会扫描字典文件来检查单词是否存在。这是主要的瓶颈，所以我一次性将所有单词读入内存，然后扫描列表。这大大提高了搜索时间，但对于八个字母的打乱词仍然非常慢。此外，我的算法基础是大量的 if 语句，使得扩展到八个字母以上非常繁琐。

我最终改进了算法以移除重复字母。这意味着不是检查 6^6 = 46656 个单词，而是检查 6! = 720 个单词。这是一个巨大的进步。岁月流逝……我决定再次编写 Jumble 程序，这次是用 C++ :)。我采用了完全相同的算法，但在使用大于八个字母的单词时仍然遇到了巨大的障碍。这个问题一直困扰着我，一个新的算法浮现在我的脑海中。我可以计算字母在打乱字母集合中出现的次数，以及字母在单词中出现的次数，然后比较两者。这效果惊人，算法得到了极大的改进。但是，我没有一个好的数据结构来查找一个单词是否属于某个打乱的字母集合。

大学课程让我学到了树，我的 Jumble 树由此诞生。现在程序加载需要几秒钟，关闭也需要几秒钟，但搜索最多只需要 26 次指针访问（最坏情况下）。我清理了代码，将其分离成类，并在此发布。显然，这个程序与这个 网站相比毫无意义，但到目前为止这是一次有趣的冒险。我确信仍有改进的空间，并期待您的反馈。

可能的未来更新

实现一个有向无环词图 (DAWG) 结构，以节省内存并减少在结构中逐项检查的时间。
测试其他算法。

历史

  • 2003 年 11 月 8 日 - v1.0
    首次公开发布
  • 2003 年 12 月 2 日 - v1.1
    更改了类名和文件名
    将 GiveWords() 的返回类型更改为 vector<CHAR*>*
    添加了 .NET 演示项目
© . All rights reserved.