Текст Twist игра с использованием рекурсии

Question

Я пишу текст Twist с использованием рекурсии на C++. Для запуска у меня есть класс Trie (содержит класс TrieNode), готовый к использованию. Моя программа сначала загружает слова из словаря и сохраняет их в объекте Trie. Затем он предложит пользователю ввести 7-буквенное слово. После прочтения всех букв мне нужно использовать рекурсию, чтобы найти все возможные комбинации букв, которые являются словами в загруженном словаре (Trie). Эти возможные слова затем сохраняются в другом Trie и распечатываются позже. Каждое возможное слово должно быть длиной не менее 3 букв и должно быть в словаре.

Я застрял там, где мне нужно написать функцию рекурсии для поиска слов, потому что почему-то я не вижу, как рекурсия может применяться в этой ситуации. Может ли кто-нибудь дать мне подсказку? Мне не нужны полные коды; Мне просто нужно, чтобы кто-то зажег эту маленькую лампочку для меня, чтобы я знал, с чего начать. Большое спасибо!

P.S. Я также сделал исследование по возвратам и проблемам 8-Queen, но до сих пор я запутался ...

Это моя основная программа:

void findWord(int i, const string &word, const Trie&lexion){ 
    //My question is, what should the base case be? 
    //I'm a bit clueless: if I start with this: 
    //if(word.length()<=1){ 
    //  return true; 
    // } 
    // else{ 
    //  return findWord(i,word.substr(1,word.length()),lexion); 
    // } 
    //I know this doesn't make sense; but I'm really lost and don't know where to start. 
} 

void main(){ 

    string word; 

    Trie lexion = Trie(); 
    lexion.loadFromFile("ospd.txt"); 
    word = getWord();//get word from the user 

    for (size_t i = 3; i <= 7; i++){ 
     findWord(i,word,lexion); 
    } 

} 

Answer 1

В основном вы хотите разделить проблему на «Могу ли я сделать слово, начинающееся с этого письма? " а затем рекурсивно спуститься к Trie для решения «Если я начну с этой буквы, могу ли я сделать слово, начинающееся с этого узла, используя подмножество остальных этих букв?», а затем преобразование результата из этого в результат для большего проблема: «Какие слова я могу сделать из этой строки, начиная с корня этого три?»

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

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

Некоторые псевегокоды:

list recursiveFind(list input, node curNode) 
    if curNode has no children 
     // we found a word! 
     return list containing ("") (so the caller knows we found a result instead of failing) 
    else 
     results = empty list 
     foreach letter in list 
      if find a node where value == letter 
      recursive_results = recursiveFind(input except for that letter, that node you just found) 
      foreach result in recursive_results 
       push (letter + result) into results 
     return results 

Надеюсь, это поможет!