php - 如何使用 PHP 以任意顺序(12 个字母，其中 6 个字母组成一个单词)进行字符搜索？

Question

我整天都在考虑这个问题，但似乎无法找到一种内存高效且快速的方法。问题是:

例如，我有这些字母:e f j l n r r t t u w x(12 个字母)

我在找这个词乌龟(6 个字母)

我如何用 php 找到全范围(12 个单词)中所有可能的单词？(或者使用 python，是否会更容易？)

我尝试过的事情:

• 使用排列:我使用排列算法使所有字符串成为可能，将它们放入数组(只有 6 个字符长)并执行 in_array 以检查它是否与我的数组中的某个单词匹配且有效单词(在这种情况下，包含 TURTLE，但有时包含两个或三个单词)。这种计算会耗费大量内存和时间，尤其是要对 6 个以上的字符进行排列时。

• 创建一个正则表达式(我不擅长这个)。我想创建一个正则表达式来检查 12 个(输入)字符中的 6 个是否在“有效数组”中的一个单词中。问题是，我们不知道 12 中的哪个字母将是起始位置和其他单词的位置。

这方面的一个例子是: http://drawsomethingwords.net/

我希望你能帮我解决这个问题，因为我真的很想解决这个问题。感谢您的宝贵时间:)

Answer 1

我在编写填字游戏编辑器时遇到过类似的问题(例如，找到所有长度为 5 且第二个位置为“B”的单词)。基本上可以归结为:

• 处理单词列表并按长度组织单词(即所有长度为 2、长度为 3、长度为 4 等的单词的列表)。原因是您通常知道要搜索的词的长度。如果要搜索未知长度的单词，可以对不同的单词列表再次重复搜索。
• 将每个单独的单词列表插入 tertiary search tree这使得搜索单词更快。树中的每个节点都包含一个字符，您可以沿着树向下搜索单词。还有专门的数据结构，例如 trie但我(还)没有探索过。

现在对于你的问题，你可以使用搜索树来编写一个搜索函数，例如

function findWords($tree, $letters) {
   // ...
}

其中 tree 是包含您要搜索的长度单词的搜索树，letters 是有效字符列表。在您的示例中，letters 将是字符串 efjlnrrttuwx。

搜索树允许您搜索单词，一次搜索一个字符，并且您可以跟踪到目前为止遇到的字符。只要这些字符在有效字母列表中，您就可以继续搜索。在搜索树中遇到叶节点后，您就找到了一个可以添加到结果中的现有词。如果您遇到不在 letters 中的字符(或者它已被使用)，您可以跳过该单词并继续在搜索树中的其他位置进行搜索。

我的填字游戏编辑器 Palabra包含上述步骤的实现(一部分是用 Python 完成的，但主要是用 C 完成的)。对于包含大约 7 万个单词的 Ubuntu 默认单词列表，它的运行速度足够快。