java - 寻求有关使用 DAWG 实现文字游戏的建议

Question

我正在尝试实现一个具有以下规则的小游戏:给定一组随机字母(例如 10)，我想找到可以由这些字母组成的所有可能的单词。我为此使用标准词典。

字母可以多次使用，但并非必须使用所有字母，只要它能生成 4 个或更多字符的单词即可。我认为这类似于解决字谜，只不过字母可以多次使用。

例如给出的字母: q r b d t e s可能的词:床上用品、甜点等。

在寻找支持 O(1) 的数据结构来检查建议的单词是否在字典中时，我发现了这个 paper随后还发现了一个有效的 Java DAWG 实现 here .

这就是我陷入困境的地方:当尝试生成可以从这些字母创建的可能单词列表时，我想知道使用 DAWG 实现是否遗漏了一些内容。我在这里看到了其他线程，建议使用 Trie 并递归地遍历节点，但我希望我可以使用 DAWG 做类似的事情。

我目前正在实现的实现是遍历字典中的所有单词，然后跳过包含不属于先前分配的字母的字母的任何单词。这可行，但速度很慢，要遍历字典中的所有单词 * 最坏情况下约为 20 个字母。

for(String word : dawg.getAllStrings()) {
     boolean blacklist = false;
     for(int i = 0; i<nonLetters.length(); i++) {
         if(word.indexOf(nonLetters.charAt(i)) >= 0) {
             blacklist = true;
             break;
         }
     }

     if(!blacklist)
         possibleWordList.add(word);
}

我尝试实现递归单词匹配，但由于该实现未公开对其 Node 实现的访问而陷入困境，不过我可以在本地更改此设置。

如果无法访问节点，我可以使用 dawg.contains(letter)，但由于需要多次使用字母，我想知道这是否真的有帮助。例如。我会从“A”开始，然后是“AA”，...停在例如20个A。

使用 Trie 会让这一切变得更容易吗？仍然相当快地找到匹配的单词，但更容易生成可能的单词列表？

是否有其他 DAWG 库公开节点遍历或具有 ref 实现来生成所有可能的单词？

感谢您的帮助或指点!

Answer 1

我觉得这是一个好办法。我向问题中引用的 DAWG 实现的 ModulatedDAWGSet 添加了一个递归方法。

使用字符串前缀调用 getWords，将字符相加。我首先实现了此方法来生成 DAWG 中的所有单词，并与 ModulatedDAWGSet.getAllStrings() 的现有方法进行比较。然后我添加了跳过不包含单词的单词，不包括可能字符列表中的字符。

private ArrayList<String> allMatchingWords = new ArrayList<String>();
private ArrayList<Character> possibleCharacters;

private void getWords(ModifiableDAWGNode originNode, String prefix) {
    NavigableMap<Character, ModifiableDAWGNode> transitionTreeMap = originNode.getOutgoingTransitions();

    for(Map.Entry<Character, ModifiableDAWGNode> transition : transitionTreeMap.entrySet())
    {
        Character c = transition.getKey();
        if(!possibleCharacters.contains(c))
            continue;

        ModifiableDAWGNode n = transition.getValue();
        if(n.isAcceptNode()) //this is a word
        {
            allMatchingWords.add(prefix + c);
        }
        getWords(n, prefix + c);
    }
}

public ArrayList<String> getAllMatchingWords(Character mustContain, ArrayList<Character> possibleCharacters)
{
    allMatchingWords.clear();
    this.mustContain = mustContain;
    this.possibleCharacters = possibleCharacters;
    getWords(sourceNode, "");
    return allMatchingWords;
}