Objective-C乱码字母解算器

Question

我试图在iphone上创建这个应用程序，给6个字母，它将输出所有可能的3-6个字母的英文单词。我已经有一本字典了，我只是想知道怎么做。

我到处搜索，只找到了python中的那些拼写求解器或那些单词搜索网格解决方案。

我认为暴力搜索可以做到，但我担心性能。代码是不必要的，一个链接到一个算法或算法本身就可以了，我想一旦我得到它，我就能够管理了。

谢谢!

Answer 1

如果您关心的是性能，这个方法可能会起到作用。它涉及到一些预处理，但将允许对字形进行近乎即时的查找。

1. 创建一个数据结构，将一个字符串键映射到一个字符串列表(我更熟悉Java，所以在这种情况下它应该是一个Map<String,List<String>>)，它将存储你的dictionary.
2. Define一个函数，它接受一个字符串，并输出按字母顺序排列的相同的字母。例如，hello将变为ehllo；kitchen将变为cehiknt。我将这个函数称为预处理部分:对于字典中的每个条目，找到该条目的关键字列表(keyify(item))并将其添加到列表中。
3. 当需要查找给定单词的变形词时，只需在列表中查找该单词的keyify即可。例如，如果输入为kitchen，则keyify将为cehiknt，在地图中查找应该会得到一个包含kitchen、chicken和我忘记的厨房的其他字形的列表:P

Answer 2

看看这个答案：Algorithm to generate anagrams..看看杰森·科恩的答案。按字母顺序排列6个字母的单词，然后浏览字典，按字母顺序排列单词并进行比较。

Answer 3

实际上我在几周前遇到了这个问题，我能找到解决它的最有效的方法是

我找到了给定字符串的所有子集(这将需要O(2^n) )

然后我查看我的字典，看看这个子集是否“用完”了这个大小的所有字符串中的所有字符

例如，给定字符串"hetre“和单词" the，hetre，her”在字典中，您可以计算所有子集

{h}{e}{t}{r}{e}{he}{ht}{hr}{he}{het}{her}{reh}..."hetre“有32个子集

然后检查这些子集中的任何一个是否与字典中的单词相似，在本例中，reh与her相似，这意味着她是要使用的单词

这是我能想到的最有效的方法

研究PowerSets并想出一种方法，可以编写“用完”字符串的函数

另一种方法是通过找出字符串的幂集并找到所有排列来暴力强制它，这将破坏性能

我的直到我开始使用第一种方法输入超过15个字符的字符串，使用第二种方法，直到7点才有问题