0

我试图在拼字游戏中为对手制定逻辑。

我做了很多思考并得出结论，我需要使用anagrams这些字谜并对照字典文件中的单词列表检查这些字谜，以查看生成的单词是否实际上是字典文件中包含的单词。

我遇到的问题是optimization。因为这个字谜使用recursion并运行多达 8 个阶乘，所以往往会生成许多在任何字典中都不存在的“垃圾”词，例如单个字母的重复。

必须进行某种检查以查看排列是否有效，而不仅仅是重复 1 个字符。到目前为止，我不知道如何快速准确地做到这一点。

在英语中，单词似乎由元音和辅音组成。我正在考虑检查一个单词是否包含至少 1 个元音和至少 1 个辅音，但是有一些例外情况，单词只能包含元音或辅音。所以这个方法似乎已经走到了窗外。

现在我可能遗漏了一些重要的东西，但是没有强制我通过所有排列的方式，我不知道如何以足够快的方式检查游戏玩法。

我的问题是：

任何人都可以提出一种可以在 100% 的时间内优化生成的排列数量的方法吗？

我不需要生成无用的，而这些结果是生成的大部分。

我相信这是一个很好的方法，但同时我相信我一定会错过一些更快、更适合我想要实现的东西。

如果有人可以建议一种方法来检查单词是否真的可行，或者如果您可以建议一种更好的方法来处理这种情况，我们将不胜感激。

谢谢。

4

2 回答 2

0

（免责声明：伪代码可能不是有效的java，即使它看起来像它）

听起来你有一堆乱七八糟的字母，想要找到所有可以用它们拼写的英文单词。

如果在对它们进行排序时它们比较相等，则两个字符串是彼此的字谜。排列候选词中的字母顺序以查看它们是否是合法的英语单词是昂贵的。相反，对字母进行排序并将其与您的单词列表进行比较：

boolean is_anagram(string word_a, string word_b){
    return sorted(word_a).equals(sorted(word_b));
}

List<string> valid_anagrams(string candidate_word){
    anagrams = new List<string>();
    foreach(string word : list_of_words){
        if (is_anagram(candidate, word)){
            anagrams.push(word);
        }
    }
    return anagrams;
}

如果您的单词列表中的单词数量小于候选单词大小的阶乘，这会更有效。例如，Words With Friends 中的合法词数约为 170,000，因此您更倾向于使用上述方法来检查长度为 9 或以上的词。

如果您打算检查大量候选词，那么您可以通过保存所有有效词的排序形式来节省时间。创建一个字典，其中键是已排序的字符串，值是英语单词列表，这些单词是该字符串的变位词。它应该如下所示：

{
    "act": ["act", "cat", "tab"],
    "abll": ["ball"],
    "aeprs": ["asper", "parse", "pears", "reaps", "spare", "spear"]
}

您可以在程序开始时构建此字典一次，如下所示：

d = new Dictionary<string, List<string>>();
foreach (string word in list_of_words){
    string key = sorted(word)
    if (!d.contains_key(key)){
        d[key] = new List<string>();
    }
    d[key].push(word);
}

然后为字符串找到有效的字谜只是访问字典的问题。

List<string> valid_anagrams(string candidate_word){
    string key = sorted(candidate_word);
    if (!d.contains_key(key)){
        return new List<string>();
    }
    else{
        return d[key];
    }
}
于 2013-09-05T16:50:18.563 回答
0

如果您想要一种快速检查字谜的方法，您可以从字典或加权图构建二叉树，然后使用字谜遍历图。这可能会在内存中变得昂贵，具体取决于字典的大小，并且在初始化时构建图形可能需要一些时间。

如果走多个图的路线，您可以为字母表中的每个字母创建一个图，然后为字典中该字母后面的每个字母创建一个 1 度连接。

所以，假设你有字典 [and, arm, ant, an, ants, antsy, Army]

你会有一个如下图：

[a][ar:1][an:3]
[ar][arm:2]
[an]["":0][and:1][ant:2]
[arm]["":0][army:1]
[and]["":0]
[ant]["":0][ants:2]
[ants]["":0][antsy:1]
[army]["":0]
[antsy]["":0]
于 2013-09-05T16:37:17.203 回答