递归实现Wordle函数生成指定格式5字母单词集的问题排查

我给wordle函数传入字符串"--pl-"，期望它返回所有第3位为'p'、第4位为'l'的5字母单词集合（理论上有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 
    
}

当前输出 #

got here
a-pl-
b-pl-
c-pl-
d-pl-
e-pl-
f-pl-
g-pl-
h-pl-
i-pl-
j-pl-
k-pl-
l-pl-
m-pl-
n-pl-
o-pl-
p-pl-
q-pl-
r-pl-
s-pl-
t-pl-
u-pl-
v-pl-
w-pl-
x-pl-
y-pl-
z-pl-
zapl-
zbpl-
zcpl-
zdpl-
zepl-
zfpl-
zgpl-
zhpl-
zipl-
zjpl-
zkpl-
zlpl-
zmpl-
znpl-
zopl-
zppl-
zqpl-
zrpl-
zspl-
ztpl-
zupl-
zvpl-
zwpl-
zxpl-
zypl-
zzpl-
zzpla
zzplb
zzplc
zzpld
zzple
zzplf
zzplg
zzplh
zzpli
zzplj
zzplk
zzpll
zzplm
zzpln
zzplo
zzplp
zzplq
zzplr
zzpls
zzplt
zzplu
zzplv
zzplw
zzplx
zzply
zzplz

你的递归逻辑存在几个核心问题：

• 递归调用的结果没有被收集，每次生成的可能单词都被丢弃
• 直接修改原字符串in会导致后续迭代的字符串被污染
• 缺失递归终止条件，没有判断字符串是否已填充完成
• 未校验生成的单词是否在字典中，也未处理floating字母规则

以下是修正后的代码：

#include <iostream>
#include <algorithm> 
#include <set>
using namespace std;

set<string> wordle(string in, const string& floating, const set<string>& dict){
    set<string> possibleList;
    
    // 递归终止条件：字符串中没有占位符'-'
    size_t dashPos = in.find('-');
    if (dashPos == string::npos) {
        // 校验：是5字母单词、在字典中、包含所有floating字母
        bool hasAllFloating = true;
        for(char f : floating) {
            if (in.find(f) == string::npos) {
                hasAllFloating = false;
                break;
            }
        }
        if (in.length() == 5 && dict.count(in) && hasAllFloating) {
            possibleList.insert(in);
        }
        return possibleList;
    }
    
    // 遍历所有小写字母替换当前占位符
    for(char c = 'a'; c <= 'z'; ++c) {
        string newStr = in;
        newStr[dashPos] = c;
        // 递归处理下一个占位符，收集结果
        set<string> subResults = wordle(newStr, floating, dict);
        possibleList.insert(subResults.begin(), subResults.end());
    }
    
    return possibleList;
}

int main(){
    string in = "--pl-";
    string floating = "ae";
    set<string> dict;
    dict.insert("joshua"); 
    dict.insert("phone"); 
    dict.insert("apple"); 
    dict.insert("aepll"); 
    dict.insert("eapll"); 
    dict.insert("ae"); 
    
    set<string> finalSet = wordle(in, floating, dict);
    cout << "got here" << endl;
    for (const string& word : finalSet) {
        cout << word << endl;
    }
    
    return 0;
}

修正说明 #

1. 递归逻辑优化：每次找到第一个'-'替换为所有字母，递归返回的结果直接插入当前集合，避免结果丢失
2. 字符串处理：传递字符串副本newStr，不修改原变量，避免污染后续迭代
3. 完整校验：递归终止时检查单词长度、字典存在性、是否包含所有floating字母
4. 终止条件明确：当字符串中没有'-'时停止递归，进入校验环节

修正后的代码会输出符合要求的单词：aepll、eapll（根据你提供的字典内容）。

内容的提问来源于stack exchange，提问作者filthysasuke