在Python中从随机字母中找词。用什么算法/已有代码？
我正在尝试编写一个单词解码器，类似于这个，想知道我应该使用什么算法来实现这个功能。另外，如果有人能找到现成的代码，那就太好了。基本上，这个功能就像一个拼字游戏的解答器，但不需要用矩阵，只是从一串字符中搜索所有可能的单词。我已经有了足够的词典。
我打算用Python或Ruby来做这个项目。非常感谢大家的帮助！
5 个回答
为了创建你的字典索引，首先需要建立一个映射（Map[Bag[Char], List[String]]）。这个映射应该是一个哈希表，这样你就可以在常数时间内（O(1)）查找单词。Bag[Char]是一个标识符，用来唯一标识一个单词，前提是字符的顺序不重要。简单来说，它就是一个从字符（Char）到出现次数（Int）的哈希表。字符是单词中的一个具体字母，而出现次数则是这个字母在单词中出现的次数。
举个例子：
{'a'=>3, 'n'=>1, 'g'=>1, 'r'=>1, 'm'=>1} => ["anagram"]
{'s'=>3, 't'=>1, 'r'=>1, 'e'=>2, 'd'=>1} => ["stressed", "desserts"]
要查找单词，你需要从输入的字符串中取出每一种字符组合，然后在这个映射中查找对应的单词。这个算法的复杂度是O(2^n)，其中n是输入字符串的长度。值得注意的是，这个复杂度和字典的长度无关。
我可能对这个游戏的理解有些偏差，但如果不考虑一些复杂的规则，比如引入“鬼牌”（通配符）字母、缺失或多余的字母、多个单词等等，我觉得以下的想法可以让这个问题变得相对简单一些。 :-(
主要想法是按照字母的顺序对单词进行索引。
比如“computer”这个词可以变成“cemoprtu”。无论随机抽取的字母是什么，都是按照这种方式排序的，然后用这个排序来寻找可能的匹配。
使用字典树结构，正如perimosocordiae所建议的，作为这些排序后的字母和相关单词（或单词ID）在“叶子”节点中的存储，单词查找可以在O(n)时间内完成，其中n是字母的数量（或者说，平均情况下会更快，因为有些单词可能不存在）。
为了进一步帮助索引，我们可以有几个表/字典，每个字典对应不同数量的字母。此外，根据统计数据，元音和辅音可以单独处理。另一个小技巧是自定义排序，把最有选择性的字母放在前面。
游戏的额外变化（比如找出由部分字母组成的单词）主要是遍历这些字母的幂集，然后检查每种组合是否在字典中。
可以引入一些启发式方法来帮助减少一些组合（例如，没有元音的组合[并且长度符合要求]是不可能的解决方案等等）。需要小心管理这些启发式方法，因为查找的成本相对较小。
我会使用一种叫做 Trie 的数据结构。这里有一个用Python写的实现例子： http://jtauber.com/2005/02/trie.py （感谢James Tauber提供的代码）