用最大分数解决拼字游戏

Question

有人问我一个问题

您将收到一份字符列表、与每个字符关联的分数和一本有效单词字典(如普通英语词典)。你必须在字符列表中形成一个单词，这样分数是最大的，并且这个单词是有效的。

我可以想出一个解决方案，用字典制作一个trie，用可用的字符进行回溯，但不能正确地表述。有人知道正确的方法或想出一个吗？

Answer 1

受程序员回答的启发(最初我认为这种方法是O(n!)所以我把它扔掉了。每个问题都需要O(词的nr)设置，然后是O(2^(查询中的字符))。这是指数级的，但在拼字游戏中，一次只有7个字母块，所以您只需要检查128种可能性！

首先要注意的是，查询或单词中的字符顺序并不重要，因此您希望将列表处理成一组字符。这样做的方法之一是‘排序’字所以"bac"，“驾驶室”变成"abc“。

现在，您接受查询，并迭代所有可能的答案。保存/丢弃每个字母的所有变体。更容易看到二进制形式: 1111保存所有，1110丢弃最后一个字母.

然后检查字典中是否存在每一种可能性(为了简单起见，散列图)，然后返回得分最高的一种。

import nltk
from string import ascii_lowercase
from itertools import product

scores = {c:s for s, c in enumerate(ascii_lowercase)}
sanitize = lambda w: "".join(c for c in w.lower() if c in scores)
anagram = lambda w: "".join(sorted(w))

anagrams = {anagram(sanitize(w)):w for w in nltk.corpus.words.words()}

while True:
    query = input("What do you have?")
    if not query: break

    # make it look like our preprocessed word list
    query = anagram(sanitize(query))

    results = {}

    # all variants for our query
    for mask in product((True, False), repeat=len(query)):
        # get the variant given the mask
        masked = "".join(c for i, c in enumerate(query) if mask[i])
        # check if it's valid
        if masked in anagrams:
            # score it, also getting the word back would be nice
            results[sum(scores[c] for c in masked)] = anagrams[masked]

    print(*max(results.items()))

Answer 2

只对字典中的每一个单词建立一个查找表。这是一次性的费用。

我的意思是:如果这个词是eat，你就把它表示为aet。这个词是tea，您表示它为aet，bubble表示为bbbelu等等。

因为这是拼字游戏，假设你有8块瓷砖(假设你想使用一块板)，你需要最大限度地检查2^8的可能性。

对于8集合中的任何瓷砖子集，您可以对这些瓷砖进行排序，并在anagram trie中查找。

最多有2^8个这样的子集，通过进行更聪明的子集生成，这可能会被优化(在重复tiles的情况下)。

如果这是一个更普遍的问题，其中2^{ tiles}可能比字典中的字谜总数高得多，那么最好使用频率计数，就像Ivaylo的答案中那样，并且可以使用多维范围查询来优化查找。(在本例中为26个维度！)

对不起，这可能对你没有帮助(我想你正在尝试做一些练习，也有一些限制)，但我希望这将有助于未来的读者谁没有这些限制。

Answer 3

如果字典条目的数量相对较少(高达几百万)，您可以使用蛮力:为每个单词创建一个32位掩码。预处理数据:如果使用字母a/b/c/./z设置一位。对于六个最常见的英语字符，如果这个字母被使用两次，etaoin就会再加一点。

为您的字母创建一个类似的位图。然后在字典中查找单词，在这些单词中，单词所需的所有位都设置在位图中，以查找可用的字母。您已经将问题简化为所有需要字符一次的单词，如果需要两次，则将六个最常见的字符减少两次。你仍然需要检查一个单词是否可以形成，以防你有一个像“泡”这样的词，而第一个测试只告诉你你有字母b，u，l，e，但不一定是3b的。

通过在检查前按点值对单词列表进行排序，第一个点击是最好的。这还有另一个好处:你可以数数你所拥有的分数，而不用费心用更多的分数来检查单词。例如，泡沫有12点。如果你只有11个点，那么根本就没有必要检查这个单词(有一个小的表，上面有第一个单词的索引和给定的点数)。

为了改进字谜:在表中，只存储具有相同点数的不同位掩码(因此我们将有冒泡和蓝色的条目，因为它们有不同的点值，而不是针对团队和配偶)。然后为每个位掩码存储所有可能的单词，可能不止一个，并检查它们。这将减少要检查的位掩码的数量。