我喜欢玩《纽约时报》的游戏。我的一天从玩Wordle开始，以填字游戏结束。我最喜欢的游戏是拼字蜜蜂，所以顺理成章地，我决定自己动手写个算法来解决这个游戏，自己破坏了玩的乐趣。
这篇帖子不是教你直接复制粘贴代码，而是介绍我在动手写代码之前考虑的一些策略。在动手写代码之前思考一些策略会有很大帮助。
怎样玩拼字游戏（如《蜂窝拼字》）？每天，游戏会给你七个字母：位于中心的金色字母，和六个外围字母。你需要用给定的字母找出能组成的单词。每个单词至少有4个字母，并且必须包含那个中心字母。你可以使用任意次数的任意字母。目标就是找出所有可能的词。
例如，对于图片中的游戏，TELL 是解中的一个词。此外，LITE、TALENT 和 ALELLE 也同样有效。但是因为它们太短，所以不符合要求。TAINT 和 ZITI 也不符合条件，因为它们缺少中心字母 L。有些词看起来符合要求但并不计入，因为它们不在《时代》官方词表中，而这个词表对玩家来说是不可获得的。比如，ITALIAN、ZELLE 和 ELLIE。
算法设计：几种方式当我开始思考如何设计算法来解决这个游戏时，我想到了几种方法。假设我们能够访问一个词表。可能不像是纽约时报的官方词汇表，但肯定是一个像这样的大词表：比如这个词表。我想到的不同方法如下：
- 对于长度为4、5、6……的每个可能的字母序列，检查该序列是否出现在单词列表中，是否仅由今天游戏板上的字母组成，并且包含中心字母。
- 对于长度为4、5、6……，仅由今天游戏字母组成并包含中心字母的每个序列，检查其是否在单词列表中。
- 对于单词列表中的每个单词，检查该单词是否包含中心字母，且单词中的每个字母是否都是中心或外圈字母。
这里有一张令人惊叹的图形展示，展示了这些方法会遍历的字符串集合。
方法1会考虑所有可能长度从4到某个限制的字母序列。如图所示，这是最大的一组可能的字符串。它包含了我们整个单词列表，因为单词是字母序列，所以。它也包括了当前游戏中可用的合法字母组合。它也包含了解决方案单词。你也可以看到，单词列表和今天的字母组合之间必须有一些交集。最后，解决方案单词就在这个交集中。
这张图片展示了几个要点。首先，许多算法问题，包括这个问题，都涉及到遍历一个搜索空间（一组可能的解决方案）来找到合适的解子集。例如，二分查找也是一个搜索空间问题的例子：搜索空间是一份排序好的数字列表，我们需要找到目标（一个特定的数字）。这与经典问题如Two Sum类似：给定一组数字，在所有可能的数字对中，找出哪些对加起来等于给定的目标值。
其次，为了找到这一类问题的有效解决方案，我们需要理解可能的搜索空间，并了解如何最好地利用它们。好的解决方案从一开始就懂得怎样利用更小的搜索空间，或者更快地减少搜索空间（二分查找就是这样），或者让每次搜索迭代更有效率（比如在解决两数之和的问题时使用哈希表）。
在这里我们有三个可供选择的搜索空间。哪些空间相对较小，哪些可以更有效地缩小搜索范围或提高搜索效率？
带着这些问题，我们完全可以拒绝第一种方法，
检查所有可能的字母序列，长度分别为4、5、6……，这些序列是否在单词列表中。并且，这些序列是否只使用了今天棋盘上的字母，且包含中心字母。
这种方法不仅使用了最大的搜索范围，对于每个字母序列还需要做三件不同的任务。因此，它需要比方法2和方法3进行更多的循环，每次循环的效率也低于其他方法。
关于方法2和方法3呢？方法2的搜索空间包括我们能从当前游戏生成的所有字母序列。方法3的搜索空间就是单词列表。哪个更大？我把两个椭圆在韦恩图中故意设置为相同大小。这是为了强调我们不应该仅仅依赖直觉来做决定，即使在这种情况下，你的直觉也可能是正确的。
让我们从方法2的搜索空间开始讨论：当前游戏中所有可以组成的字母序列。考虑当前游戏中可以组成的长度为4的字母序列。那么，这样的序列共有多少个呢？我们可以用补集计数法来计算出这个，这是一种巧妙的方法，步骤如下。首先，计算出可以组成的长度为4的字母序列有多少个。游戏中有七种字母，所以是7⁴。这个数字包括不包含中心字母、只包含一次、两次、三次或四次中心字母的所有序列。但一个字母序列必须包含中心字母，因此，从这个总数中减去不包含中心字母的序列数量。那么，不包含中心字母的序列有多少？也就是说，可以组成的4个字母序列的数量是6⁴。因此，长度为4且包含至少一个中心字母的字母序列共有7⁴ — 6⁴个。
一般来说，对于长度为 k 的字母组合，有 7^k — 6^k 种可能的组合。因此，组合的总数看起来像 (7^4 — 6^4) + (7^5-6^5) + (7^6-6^6) + ... 直到我们决定停止计算。也许我们停在 k=10。也许 k=20。也许我们将 k 设为词表中最长词的长度。无论何时停止，这将是一个非常大的数，实际上是一个 指数级大的 数。如果我们计算到 10，就有 256,994,905 个字母组合要检查。如果我们计算到 12，将超过 130 亿。
那比单词列表的规模要大得多。例如，英语维基词典约有80万词条。因此，由于方法2和方法3在每次迭代中所做的工作量差不多（检查一个序列是否在单词列表中，或检查一个单词是否使用了中心字母和周围的字母），我们也应该放弃方法2。这样只剩下方法3，即在单词列表中查找单词。
预处理及查询操作第三种方法的算法可能如下：
对于词列表中的每个单词：
- 将单词中使用的不同字母存为letters
- 如果中心字母不在letters里，就跳过这个单词
- 如果letters里的字母有任何一个是非中心和非外圈字母，就跳过
- 如果到了这一步，就把这个单词加入到解决方案单词列表中我们可以添加一些优化，例如立即跳过所有少于4个字母的单词，或者一旦发现某个单词包含超过7个不同的字母就立即停止遍历。即便如此，在最坏的情况下，这里的运行时间是 O(W * L)，其中 W 是列表中的单词数量，L 是每个单词的平均长度。（可以将 W * L 理解为单词列表中的总字符数。）
好消息是：这并不是指数级！而是完全行得通！
但是我们可以做得更好吗？可以的！
目前这种形式下，此算法将做 O(W * L) 的工作来解决今天的每日拼字游戏。明天它还会做同样的 O(W * L) 的工作。同样的事情会在接下来的每一天重复。然而，其中很多工作是在重复进行的，特别是每天都在重复找出每个单词中使用的独特字母。这项工作每天都是完全一样的，因为单词列表从不改变。这项工作不会因为当前游戏的字母不同而改变。
为了避免这种重复的工作，我们需要一个更好的词汇表。我们可以在尝试解决任何游戏之前，先完成所有这些准备工作，然后将其全部保存到一个新列表里，或者保存为查找表或类似的 JSON 文件。
{
"aardvark": "ADKRV",
"bonobo": "BNO",
"noob": "BNO",
...
"ziti": "ITZ",
}这个预处理仍然需要 O(W * L) 的时间复杂度，但只需做一次。一旦完成，每次解决当天的游戏挑战时，我们都可以重复利用这个文件，而无需重新进行这项工作。我们还可以在预处理中加入一些优化，比如丢弃那些太短或含有超过7个不同字母的单词。
之后，解决当天的游戏就只需要这样一个查询函数了。
对于wordList中的每个单词：
// 在常数时间内查找预计算的唯一字母！
- 将letters设置为wordList[word]
- 如果中心字母不在letters里，就跳过这个单词
- 如果letters中的任何字母既不是中心字母也不是外层字母，就跳过
- 如果能执行到这里，就把这个单词加到解决方案的单词列表里这个查询函数查找不同字母的操作时间为 O(1)。假设我们在预处理阶段做了优化，最多有 7 个不同字母。因此，查找中心字母的操作同样为 O(7) = O(1)，验证每个不同字母是否在游戏字母集中的操作也是 O(7) = O(1)。因此，我们的查询函数现在的时间复杂度为 O(W * 1) = O(W)，不再是 O(W * L)。
这与单词列表的大小成正比，真是太好了！
但我们做得更好吗？能！
翻字典回想一下，我们对单词列表进行了预处理，将其转化为如下字典（也就是对单词列表进行了一些初步处理，以便更好地组织和使用）。
{
"aardvark": "ADKRV",
"bonobo": "BNO",
"noob": "BNO",
……
"ziti": "ITZ",
}注意，“bonobo” 和 “noob” 都用了相同的字母组合：BNO。类似的还有“boon” 和 “bonbon”。想想其他你熟悉的单词，你可能会发现这样的情况非常普遍。
现在考虑一下。如果我们像下面这样在预处理时翻转了字典，把字典中的键值对翻转过来，这样我们能得到什么好处呢？
{
"ADKRV": ["食蚁兽"],
"BNO": ["boon", "邦邦", "bonobo", "新手", ... ],
"ITZ": ["ziti", ... ],
"AELT": ["elate", "late", "latte", "tale", "teal", "tattletale", ... ],
...
}在这本词典中，每个键是一个字母组（用字符串表示），每个值是由该字母组中的每个字母至少使用一次构成的单词的列表（且只能使用该组中的字母）。同样地，在预处理时，我们可以确保每个字母组中的字母不超过7个，并且每个列表中的单词长度至少为4。
这怎么帮到我们了呢？再来看看我们的棋盘，
（如果上下文是指董事会而非棋盘，请将“棋盘”改为“董事会”。）
假设我们要找的是包含字母AEILNTZ的所有单词，这些单词使用了棋盘上的每个字母。这次查找就可以在常数时间内给出所有符合条件的全字母词的列表。
而且我们不必止步于此。我们可以查找不包含N的所有字母组合的单词，只需查找包含AEILTZ的单词即可。或者查找包含L、E和A的单词，查找包含AEL的单词。
实际上，我们可以把包含中心字母的字母组合，从2个字母一直到7个字母，都找出来。然后查字典，把能用这些字母组成的单词都找出来，并把它们加进列表里。
最后，我们就能得到一个完整的解决方案了！
花点时间来证明这个方法有效。想象一下今天游戏里所有可能的解词。每个词都是由游戏中的字母组成。所以，如果我们系统地检查所有可能的字母组合，就能找到所有可能的词。
这可能看起来像这样的算法：
对于每个包含中心字母且长度大于等于2的字母组合：
- 将字母组合排序并转换为字符串。
- 在字典中查找该字符串，得到一个单词列表。
- 将列表中的每个单词添加到解词集合中。
确实如此。字母序列不利，因为它们会导致搜索空间呈指数级膨胀。我们现在讨论的是字母组合。组合和序列的区别在于，序列讲究顺序，而组合不讲究。比如，ABC、ACB、BAC和BCA都被视为不同的序列，但是它们都只算作一个组合：ABC。我们的序列也可以包括像AAA和ABB这样的重复字母，但在组合中每个字母只能用一次。所以，组合的数量会比序列少很多。
之前的那些方法与我现在向你推荐的方法之间还有一个关键的不同之处。之前，我们必须考虑长度为4、5、6……还可能更长的字母串，没有一个明确的长度限制，随着长度的增加，搜索空间的大小呈指数级膨胀。而这个解决方案则考虑具有明确限制的组合，我们希望得到长度为2到7的组合。
这意味着新的搜索空间真的超级小。咱们来看看它到底有多小。
游戏中使用7个字母能组成多少种组合呢？嗯，游戏中只有7个字母，所以这很简单，我们必须要使用所有的字母，所以只有一种组合。
长度为6的组合有多少种？首先，我们必须包含中心字母。这样就剩下5个字母需要选择了。组合中不能有重复的元素，所以我们必须从剩下的6个字母中选择。你可以算出有6种方式来完成选择。
你可能在统计课上学过这个叫做“n选k”的计算公式。对于每个组合长度 k = 2, 3, …, 7，我们都要包含中间的字母。然后我们可以用剩下的六个字母做 6 选 k-1 的组合。
下面是每种组合长度的计算结果。我使用了一个在线计算器来计算，这个计算器是“n选k计算器”，可以在这个网站找到: n choose k计算器。
- 长度2：6选1=6
- 长度3：6选2=15
- 长度4：6选3=20
- 长度5：6选4=15
- 长度6：6选5=6
- 长度7：6选6=1
- 所有组合的总数：6 + 15 + 20 + 15 + 6 + 1 = 63
所以用这种方法，我们从一个包含数十亿个元素的庞大搜索空间，变成了只需要考虑 63 个元素的搜索空间。
运行时分析回想我们新开发的查询算法。
对于每一个长度大于等于2且包含中心字母的字母组合：
- 将字母组合排序并转换为字符串
- 在字典中查找该字符串，获取对应的单词列表
- 将列表中的每个单词添加到解词集中总共有63种组合方式，循环会运行63次，每次迭代中我们都会...
- 对字母组合进行排序整理。最大的组合长度为7个字母，因此时间复杂度为
O(7 log 7) = O(1)。 - 将组合转换为字符串。这需要的时间为
O(7) = O(1)。 - 在字典中查找该字符串键。这也同样为
O(1)。 - 将列表中的每个单词添加到解决方案中。运行时间会根据列表长度有所不同。
处理最后一步有点棘手，但假设当我们完成时，解决方案中的单词数为 S。在整个过程中，我们总共会花费 O(S) 时间来把单词加入解决方案里。我们将会独立计算这个时间，而不是将其与迭代次数相乘。
总之，我们可以将运行时间表示为 O(63) + O(S)，这可以简化为 O(S)，其中 S 是解的大小。
一个缺点是，在这些解决方案包含很多单词的日子，算法运行时间会更长。然而，拼写蜂的解决方案通常少于100个词，相比之下，之前的运行方式需要遍历数十万个词列表条目，现在的运行时间要好得多。
完整的算法及其实现以下是完整解决方案的伪代码。
预处理算法
假设 wordList 是一个包含纽约时报单词列表的更大单词列表的超集。一个例子可能是来自 Wordnik 的这个很棒的单词列表：https://github.com/wordnik/wordlist/blob/main/wordlist-20210729.txt。在预处理开始时，我们已经以某种方式将该列表加载到内存中，或者我们正在逐词读入。
首先，我们进行一次预处理，生成字母组合到单词的词典的过程。
// 预处理的时间复杂度为 O(W * L)
// 其中 W 代表 wordList 中单词的数量
// L 是 wordList 中单词的平均长度
输入：单词列表（wordList）
输出：预处理后的字典，将字母集映射到由这些字母集组成的单词列表
创建一个空字典 D
对于 wordList 中的每个单词：
- 如果单词长度小于 4，跳过该单词
- 将 letters 设为单词中的不同字母
- 如果 letters 的长度大于 7，跳过该单词
- 就地对 letters 按字母顺序进行排序
- 如果排序后的 letters 已经是 D 的键，则将单词添加到 D[letters] 对应的列表中
- 否则，如果 letters 不是 D 的键，则 D[letters] = [word]
返回 D 或将其写入文件，视情况而定。算法查询
假设我们已经把字典 D 读入内存中，并且查询算法可以访问这个字典。
// 查询算法：时间复杂度为 O(S)，其中 S 表示解列表的长度
输入：一个中心字母和一个包含 6 个外围字母的列表
输出：解单词列表
创建一个空列表 L
从 1 到 6（含）：// 使用 i 个外围字母
对于每个长度为 i 的外围字母组合：
- 将中心字母添加到每个组合中
- 对组合进行排序
- 从字典 D 中查找组合
- 如果组合在 D 中存在作为键，
将 D[组合] 中的每个单词添加到 L
返回列表 L实施
我会把这个留给你来做。如果你用 Python，你可以用 itertools.combinations() 生成外层字母的组合。
坑和问题
找到一个好的词表并进行适当的调整是使这一切真正奏效的关键。如果词表太大，它会产生一些理论上有效但实际上游戏不接受的答案。如果词表不够全面，它将不包含《时代周刊》的词表中的某些单词，解决方案将不完整。
但你真的想要一开始就能完美解决问题的算法吧？那岂不是太没意思了吗？