c++ 使用递归打印所有可能的5个字母的单词

8ehkhllq  于 2022-11-27  发布在  其他
关注(0)|答案(2)|浏览(170)

我把一个字符串“--pl-”传递给函数wordle。我希望函数返回一个字符串集合,其中包含所有可能的5个字母的单词,第3个字母为“p”,第4个字母为“l”。这意味着该集合将返回26^3个不同的字符串。
我试图使用递归来做这件事,但不知道如何。

#include <iostream>

#include <algorithm> 
#include <map>
#include <set>
// #include "wordle.h"
// #include "dict-eng.h"
using namespace std;

// MOST UP TO DATE

// Add prototypes of helper functions here

// Definition of primary wordle function
set<string> wordle(string& in, string& floating, set<string>& dict){
    set<string> possibleList;
    int length = in.length();
    

    // iterate over each letter
    
    for(int i = 0; i<length;i++){

        // only if -
        
        if (in[i] == '-'){
            
            for(int j = 97; j<=122; j++){
                in[i]=char(j);
                possibleList.insert(in);
            }
            set<string>::iterator itr;
            for (itr = possibleList.begin(); itr != possibleList.end(); itr++)
            { 
                auto S = *itr;  //copy of *iter
                wordle(S, floating, dict);  //use S
            }
        }
    }
    // if we reach here, that means that we now have all possibilities in the set
    
    return possibleList;
} // end of function
    
    
int main(){
    
    string in = "--pl-";
    string floating = "ae";
    set<string> dict;
    // set with 6 strings, should only return 2 of these
    dict.insert("joshua"); // same
    dict.insert("phone"); //diff
    dict.insert("apple"); //same
    dict.insert("aepll"); //same
    dict.insert("eapll"); //same
    dict.insert("ae"); // diff
    
    set<string> finalSet = wordle(in, floating, dict);
    cout << "got here" << endl;
    set<string>::iterator itr;
    for (itr = finalSet.begin(); itr != finalSet.end(); itr++)
    { 
        cout << *itr << endl;
    }
    
    
    return 0;
    
    // how this works:
    // take all possible strings of the form of size n
    // then remove all requirements not met 
    
}

所发生的情况是它打印以下内容:
在此获得以下信息:一个简单的例子是,一个人的一生中,他的一生中,他的一生中,他的一生中,他的一生中,他的一生,他的一生,他的一生,他的一生,他的一生,他的一生。

oxf4rvwz

oxf4rvwz1#

我忽略了floatingdict参数。下面是一个迭代(非递归)解决方案,您可以从它开始:

#include <vector>
#include <string>

std::vector<std::string> combine(
  const std::vector<std::string>& acc, const std::string& next) {
  std::vector<std::string> result;
  for (const auto& x: acc) {
    for (auto y: next) {
      result.push_back(x + y);
    }
  }
  return result;
}

std::string symbols = "abcdefghijklmnopqrstuvwxyz";

std::vector<std::string> wordle(const std::string& in) {
  std::vector<std::string> result{""};
  for (auto c: in) {
    result = combine(
      result,
      c == '-'? symbols : std::string(1, c));
  }
  return result;
}

你可以用你的模式来称呼它,例如wordle("---pl-")

frebpwbc

frebpwbc2#

你的代码中的问题是你没有使用wordle中嵌套递归调用的结果。换句话说,当你在“0级”填充possibleList时,你就有了wordle的嵌套调用,但它目前是无用的,因为它所做的一切--它只是在里面做。这就是为什么你会得到你所描述的结果。
具体来说,会发生以下情况:
在0级,你用“a--pl-",“B--pl-",...,“zzzplz”等变量填充列表,并将它们收集到possibleList中。无论你有递归调用,你的possibleList在0级仍然是相同的,它稍后被返回-这就是你得到的结果。
此外,你需要改变迭代不同变体的方式,一般来说,可能是这样的(抱歉没有给出C语言的具体代码--很久没有使用if了):
1.首先在字符串中搜索第一个出现的_,记住它的位置。
1.然后遍历所有可能的字符串,并用一个新的字符串替换这个_,从而生成一个字符串的副本。
1.对于每一个新字符,你都可以用这个新字符串进行嵌套调用。你也可以传递当前位置,这样它就知道从哪里开始,但这更多的是一种优化。
1.嵌套调用将返回一组组合。您需要将其与当前级别的一组组合合并。
1.然后返回累积集。
请注意,您不需要在方法中显式迭代字符串中的所有_,因为它将以递归方式完成:每个新级别在字符串中找到它自己的第一个_

UPD:伪代码

FUNCTION wordleRecursive(str, start=0):
  possibleList = []
  foundPlaceHolder = False
  
  FOR (i=start; i<str.length; i++):
    IF str[i] == '_':
      foundPlaceHolder = True
      FOR (j=97; j<122; j++):
        newStr = copy(str)
        newStr[i] = char(j)
        nestedList = wordleRecursive(newStr, i + 1)
        possibleList = merge(possibleList, nestedList)
      
      // We need to find only first occurance
      BREAK 

  // This is needed if the substring does not contain "_" anymore
  // in this case we need to return the list with a single item,
  // Containing the str itself.
  IF NOT foundPlaceHolder:
    possibleList = [str]

  RETURN possibleList

相关问题