利用DAWG实现文字游戏的几点建议

Question

我试着用以下规则来实现一个小游戏:给定一组随机字母(例如10)，我想找出所有可以从这些字母中形成的单词。我用的是一本标准字典。

字母允许多次使用，而不是所有的字母都必须使用，只要它产生4个字符或更多字符的单词。我认为这类似于解字谜，只是字母可以多次使用。

例如:给出的信件:Q，r，b，d‘’的单词:床上用品，甜点，等等。

为了寻找支持O(1)的数据结构来检查字典中是否有建议的单词，我找到了这个纸，随后还找到了一个工作的Java实现这里。

是我被困在这里的地方:当我试图生成一个可以从这些字母创建的单词列表时，我想知道我是否缺少了使用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(字母)，但是由于需要多次使用字母，我想知道这是否真的有帮助。我会从'A‘开始，然后'AA'，…在例如20A停车。

如果有一个Trie，这一切会更容易吗？找到匹配的单词仍然相当快，但是更容易生成一个可能的单词列表？

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

谢谢你的帮助或指点！

Answer 1

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

使用字符串前缀调用getWords，将字符相加。我首先实现了这一点，以生成DAWG中的所有单词，并将其与现有的ModifiableDAWGSet.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;
}

Answer 2

我有个主意，我不确定，但希望能帮你。首先，创建字典作为一个工作键，关键将是所有的字母，该词所包含的字母顺序。例:经典的-> acils，字母-> elrt。类似于随机字符串。你可以为你的节目准备这个。并获得浏览O (n)复杂度字典所需的一切

for(Word word : dawg.getAllStrings()){
    if(randomString.contains(word.getKey()))
    possibleWordList.add(word);
}