Поиск предложений по реализации игры в слова с помощью DAWG

Question

Я пытаюсь реализовать небольшую игру со следующими правилами: учитывая набор случайных букв (например, 10), я хочу найти все возможные слова, которые можно составить из этих букв. Я использую для этого стандартный словарь.

Буквы можно использовать несколько раз, и не все буквы должны использоваться, если это приводит к словам, состоящим из 4 или более символов. Я думаю, что это похоже на решение анаграмм, за исключением того, что буквы можно использовать несколько раз.

Например, указанные буквы: q r b d t e s Возможные слова: постельное белье, десерт и т. Д.

В поисках структуры данных, поддерживающей O(1) для проверки, если предложенное слово в словаре, я нашел эту бумагу, а затем и нашел рабочую реализацию Java DAWG здесь.

Вот где я застрял: пытаясь сгенерировать список возможных слов, которые можно создать из этих букв, мне интересно, не упускаю ли я чего-то с помощью реализации 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), но с требованием использовать буквы несколько раз мне интересно, действительно ли это поможет. Например, я бы начал с "А", затем "АА",... остановившись, например, на 20 А.

Было бы все это проще с Trie? По-прежнему довольно быстро найти подходящие слова, но проще составить список возможных слов?

Существуют ли другие библиотеки DAWG, которые предоставляют обход узлов или имеют реализацию ref для генерации всех возможных слов?

Спасибо за любую помощь или указатели!

Answer 1

Думаю, это хороший способ. Я добавил рекурсивный метод в ModifiableDAWGSet реализации DAWG, упомянутой в вопросе.

getWords вызывается с префиксом String, складывающим символы. Сначала я реализовал это для генерации всех слов в 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);
}