3

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

例如，我有这些字母：efjlnrrttuwx（12 个字母）

我正在寻找这个词 TURTLE（6 个字母）

如何使用 php 在全范围（12 个单词）中找到所有可能的单词？（或者使用 python，如果这可能会容易得多？）

我尝试过的事情：

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

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

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

我希望你能帮助我解决这个问题，因为我真的很想解决这个问题。谢谢你所有的时间:)

4

4 回答 4

2

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

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

现在对于您的问题，您可以使用搜索树编写搜索功能，例如

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

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

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

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

于 2012-03-15T18:52:46.550 回答
1

可能有更好的方法，但这只是我的想法：

我假设您有一个单词数据库（即字典）。将字段 az 添加到数据库表中。编写一个脚本，汇总单词中每个字母的计数，并将它们作为整数写入 az 字段中。IE 的气球，表格看起来像：

id    name       a    b  ...  l  ...  n  ...  o
1     balloon    1    1       2  ...  1  ...  2

然后，当用户输入一个单词时，您计算该单词中每个字符的数量并将其与数据库匹配。

// User enters 'zqlamonrlob'
// You count the letters:
a b c d e f g h i j k l m n o p q r s t u v w x y z
1 1 0 0 0 0 0 0 0 0 0 2 1 1 2 0 1 1 0 0 0 0 0 0 0 1

// Query the database
$sql = "SELECT `name` FROM `my_table` WHERE `a` <= {$count['a'] AND `b` <= {$count['b'] ...}";

这将为您提供使用用户输入的部分或全部字母的单词列表。

于 2012-03-15T18:48:47.877 回答
1

这是一个正则表达式，只是为了表明它可以（但不一定应该）完成：

preg_match('/^(?:t()|u()|r()|t()|l()|e()|.)+$\1\2\3\4\5\6/i', 'efjlnrrttuwx')

火柴。

它是如何工作的？如果前面的字母匹配，则空的捕获括号始终匹配。正则表达式末尾的反向引用确保每个字符都参与了匹配。所以，

preg_match('/^(?:t()|u()|r()|t()|l()|e()|.)+$\1\2\3\4\5\6/i', 'efjlnrrtuwx')

（正确）将不匹配，因为字符串中只有一个t，但正则表达式需要两个不同t的 s。

问题是，当然，正则表达式引擎必须检查许多排列才能得出这个结论。虽然成功的匹配可能很快（第一种情况下正则表达式引擎的 175 步），但不成功的匹配尝试可能代价高昂（第二种情况下 3816 步）。

于 2012-03-15T21:25:08.847 回答
0

我认为你需要从相反的方向解决这个问题。

循环遍历您的单词列表，测试具有指定字符数的单词，以查看单词字符是否在指定字符集中。

于 2012-03-15T18:55:08.427 回答