我正在尝试在给定 6 个字母的 iphone 上创建这个应用程序，它将输出所有可能的 3-6 个字母的英文单词。我已经有一本字典，我只想知道怎么做。
我四处搜索，只找到了那些在 python 中的拼字游戏求解器或那些单词搜索网格解决方案。
我认为蛮力搜索会做，但我担心性能。代码不是必需的，一个算法的链接或算法本身就可以了，我想我一旦得到它就可以管理。
谢谢！
问问题
1771 次
3 回答
1
如果您担心性能，这种方法可能会奏效。它涉及一些预处理，但允许几乎即时查找字谜。
创建一个将字符串键映射到字符串列表的数据结构（我更熟悉 Java，所以在这种情况下它会是 a
Map<String,List<String>>）这将存储您的字典。定义一个函数，该函数接受一个字符串并输出按字母顺序排列的相同字母。例如，
hello会变成ehllo;kitchen会变成cehiknt. 我将此功能称为keyify(word)这是预处理部分：对于字典中的每个项目，找到该项目的键 (
keyify(item)) 的列表并将该项目添加到列表中。当需要查找给定单词的字谜时，只需查找
keyify该单词的列表即可。例如，如果输入是kitchen，keyify则将是cehiknt，在地图中查找应该会生成一个列表，其中包含kitchen，chicken以及我忘记的任何其他厨房字谜：P
于 2011-07-27T03:20:53.510 回答
0
看看这个答案：生成字谜的算法。看看 Jason Cohen 的答案。将 6 个字母的单词按字母顺序排列，然后翻阅字典并按字母顺序排列该单词并进行比较。
于 2011-07-27T03:16:07.607 回答
0
几周前我实际上遇到了这个问题，我能弄清楚如何解决它的最有效方法是
我找到了给定字符串的所有子集（这需要 O(2^n) ）
然后我查看了我的字典，看看子集是否“用完”了该大小的所有字符串的所有字符
例如，给定字符串“hetre”和单词“the, there,her”在您的字典中，您可以计算所有子集
{h}{e}{t}{r}{e}{he}{ht}{hr}{he}{het}{her}{reh}...“hetre”有 32 个子集
然后检查这些子集是否与字典中的单词相似，在这种情况下，reh 与她相似，这意味着她是要使用的单词
这是我能想到的最有效的方法
研究PowerSet并想出一种方法可以编写“用完”字符串的函数
另一种方法是通过找出字符串的功率集并找到所有排列来强制它，这将破坏性能
在我开始使用第一种方法使用第二种方法输入超过 15 个字符的字符串之前，我的没有给我带来问题，直到 7 点我才遇到问题
于 2011-07-27T03:38:01.077 回答