如何搜索在单词上添加字母的所有可能组合？

Question

我一直被这个问题困扰。我正在尝试做的是看看使用某种二进制搜索方法可以在单词中添加字母的几种可能方式。

例如，假设我有一个长4个字母的单词，那么这个单词是：----

现在，我想了解所有可能的方法，可以在此单词上添加一个“ Y”。然后所有可能的组合都是2 ^ 4，看起来像：

---------Y---YY-Y---Y-Y-YY--YYY--Y-Y-Y-YYYY--YY-YYYY-YYYY

如何获得所有这些组合？然后，我打算将所有这些组合添加到一个字符串列表中，然后将其用于与一组单词进行比较。

Answer 1

为什么不进行递归完整搜索？类似于以下内容的东西应该起作用：它是这样的：在位置i，您可以插入'Y'或'-'。做出决定后，您可以将其附加到长度i-1的所有可能组合中。

vector<string>  generate_p(const int n){
    vector<string> ans;
    if(n==0)
    {
        ans.push_back("");   
    }
    else
    {
        cout<<n<<endl;
        auto v = generate_p(n-1);    
        for(size_t i = 0 ; i < v.size() ; i++){
            ans.push_back("Y"+v[i]);
            ans.push_back("-"+v[i]);
        }
    }
    return ans;   
}

Answer 2

您可以将其视为二进制问题。这是所有从0000到1111的数字（以二进制为单位）。然后将1映射到Y