关于在词典中查找所有有效词的算法问题
给定一个字典（只是一个字符串列表）。
您收到来自外部来源的未知数量的信件的Feed。 给定一串字母，您将如何列出您可以从这些字母的任何组合中制作的所有有效单词（来自diciontary）。
所以如果你收到：abpplead
你应该找到苹果，坏，垫，铅等。
我知道没有最好的答案。 但是有哪些合理有效的方法，使用什么数据结构等等。
此外，假设您可以预处理输入，因此您可以选择将输入字母存储在您想要的任何数据结构中。
将字典放入特里。 然后将字母放入由其字符值索引的计数器数组中，保持每个字母的计数（让这称为[]。 然后深入遍历trie第一个搜索顺序，在向下移动时递减每个字母的计数[letter]值，并在返回的路上递增它。 现在，任何时候计数[字母]即将消极，停止并向后移动。 每次到达单词终止符时，输出结果。
如果您不允许对该字符串列表执行任何预处理，那么就没有“合理有效的解决方案”：您将不得不遍历整个列表，检查每个单词是否可以组成为必需的（即，它的签名，见下文，统一小于传入的束的签名）。 O（N）表示列表中的N个字符串。
如果允许预处理（你预处理一次列表然后回答几个查询，足以分摊预处理成本），那么对于列表中的每个单词都会产生一个“签名”，这是26个整数的数组，用于计算每个字母的出现次数在字符串中（假设它是英文和不区分大小写 – 扩展很明显）。 当你去的时候，建立一个从每个签名到具有该签名的单词列表的地图。 对于HashMap，此预处理大致为O（N）。
现在，给定一堆K个字母，您可以计算束的签名并在地图中查找具有该签名的每个单词列表; 重复所有无均匀签名（O（2 ^ K）是这里的上限）。 所以对于Z这样的查找，你需要支付O（N + Z * 2 ^ K）（相对于O（Z * N）而不进行预处理），所以你获得（对于足够大的数字，以便O（）估计有意义）如果N> 2 -1K-。
对于字典中的每个单词，检查它是否来自您只有的字母。
要检查这一点，您可以创建辅助结构，如dict x[letter: amount] ，使用给定字母的数量初始化它，然后：
for each word 'w' in dictionary init x from given letters for each letter `ch` in word `w` --x[ch] if x[ch] < 0 break, do not add w to result result.add(w)
1.为字典中的每个单词创建树结构。 每个字母上的树枝，例如树的第一层是字母az，下一层也是az，如果有任何使用该组合的单词，等等。树的叶子是单词。
然后，当你得到字母组合时，只需从第一个字母的所有选项开始，沿着该分支向下移动树，然后搜索第二个字母的所有选择，等等。
虽然这看起来很有意义，但并非所有的组合都是可能的，你会发现无效的分支很快被修剪掉了。
将字典预处理为dawg ，然后使用其中一种dawg-walking算法来搜索子字符串。 我有一些基本的ruby代码，可以在这里使用dawg; 事实certificate它在实践中太慢了，所以我转移到ocaml（未发布），但它应该让你知道如何找到字谜。 对于subanagrams，即使你的包不是空的，也只需为一个单词结尾添加一个额外的检查。
使用rete算法并将问题视为基于规则的域中的问题。 单词是规则（用自己的字母作为规则模式）。 对于给定的每组字母，您应用规则库，所有匹配的单词将“fire”。 冲洗并重复。 🙂
[编辑ps]
这里的动机是这样的：“Rete的表现在理论上与系统中的规则数量[在你的案例中的字典中的单词]无关”。