我想从一个短语中找到所有可能的字谜，例如，如果我输入“Donald Trump”，我应该得到“Darn mudplot”、“Damp old runt”以及可能还有数百个。
我有一本大约 100,000 个单词的字典，没有问题。
但我能想到的唯一方法是循环遍历字典并将可以从输入构建的所有单词添加到列表中。然后循环遍历列表，如果单词长度小于输入的长度，则再次循环遍历字典，添加可以由剩余字母组成的所有可能的单词，使其等于或小于输入的长度。并继续循环，直到我拥有长度等于输入长度的有效单词的所有组合。
但是这是 O(n!) 的复杂度，并且几乎需要永远运行。我已经尝试过。
有什么方法可以解决这个问题，从而降低复杂性吗？我可能在网上找到了一些关于 Perl 的东西，但我绝对无法阅读 Perl 代码，尤其是 Perl Golf。
最佳答案
我喜欢你将单词列表过滤为仅可能由输入字母组成的单词的想法，并且我喜欢尝试将它们串在一起的想法，但我认为你可以进行一些主要的优化落实到位可能会大大加快速度。
对于初学者来说，我不会选择一个单词，然后重新扫描整个字典以查找剩下的内容，而是考虑在开始时进行一次过滤，以查找可以用您拥有的字母组成的所有可能的单词。你的字典可能会非常庞大(我怀疑超过 150,000 个)，因此在每个决策点之后重新扫描它是完全不可行的。一旦你有了可以在字谜中合法使用的一组单词，接下来的问题就是找到可以使用它们的哪些组合来形成句子的完整字谜。
我首先会查找与目标字谜相对应的无序单词列表，而不是所有可能的有序单词列表，因为要查找的单词要少得多。一旦获得无序列表，您就可以很快地从它们生成排列。
为此，我将使用回溯递归，在每个点上维护剩余字母计数的直方图。您可以使用它来过滤掉无法再添加的单词，这基本上可以节省您每次检查整个词典的成本。我想这个递归会陷入很多死胡同，并且您可能会毫不费力地找到所有答案。
在此过程中您可能会考虑一些其他启发式方法。例如，您可能希望首先从较大的单词开始，以提取尽可能多的字母并保持较低的分支因子。为此，您可以将单词列表从最长到最短排序，然后按该顺序尝试单词。您也可以尝试首先使用最受约束的字母来减少分支因子。这些启发式方法在实践中可能会非常有效。
总体而言，您仍在考虑最坏情况下的指数工作，但对于较短的字符串来说应该不会太糟糕。
关于Python:查找句子的所有字谜，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40724726/