如何使用C++实现从多个字符串各取字符生成所有排列组合

假设给定字符串"abc"、"def"、"ghi"，需要从每个字符串中各选取1个字符拼接成新单词，生成所有符合要求的组合结果。
以示例中的三个字符串为例，最终输出结果应为：

"adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"

vector<string> wordset;

for(int i = 0; i < digits.size(); i++ )
{
    wordset.push_back( latters[digits[i] - '0'] );
}

           
for(int i = 0; i < wordset.size()-2; i++ )
{
    string word = wordset[i];
    for(int j = 0; j < word.size(); j++ )
    {
        string combn = "";
        combn += word[j];
                        
        for(int k = 0; k < wordset[i+1].size(); k++ )
        {
            combn += wordset[i+1][k];

            for(int l = 0; l < wordset[i+2].size(); l++ )
            {
                combn += wordset[i+2][l];

                ans.push_back(combn);
                combn = "";
                combn += word[j];
                combn += wordset[i+1][k];

            }

        }
    }
}

• 硬编码3层循环，仅支持输入3个字符串的场景，无法适配输入数量动态变化的情况
• 拼接字符串的重置逻辑冗余，容易引发拼接错误
• 注意原代码中字母映射的变量名latters为拼写错误，正确拼写应为letters

通用方案（适配任意数量输入字符串） #

采用回溯法实现，适配性更强，可支持任意长度的输入：

#include <vector>
#include <string>
using namespace std;

vector<string> ans;
// 回溯参数说明：当前处理到第index个字符串，当前已拼接的组合为current
void backtrack(int index, const vector<string>& wordset, string current) {
    // 已处理完所有字符串，当前组合符合要求加入结果
    if (index == wordset.size()) {
        ans.push_back(current);
        return;
    }
    // 遍历当前字符串的所有可选字符
    for (char c : wordset[index]) {
        current.push_back(c);
        backtrack(index + 1, wordset, current);
        // 回溯，移除刚加入的字符，尝试下一个可选字符
        current.pop_back();
    }
}

vector<string> letterCombinations(string digits) {
    ans.clear();
    if (digits.empty()) return ans;
    // 手机键盘字母映射表
    vector<string> letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> wordset;
    for (char d : digits) {
        wordset.push_back(letters[d - '0']);
    }
    backtrack(0, wordset, "");
    return ans;
}

固定3个输入的简化方案 #

如果确定输入永远只有3个字符串，也可以直接简化循环逻辑：

vector<string> letterCombinations3(string digits) {
    vector<string> ans;
    if (digits.size() != 3) return ans;
    vector<string> letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    string s1 = letters[digits[0] - '0'];
    string s2 = letters[digits[1] - '0'];
    string s3 = letters[digits[2] - '0'];
    for (char a : s1) {
        for (char b : s2) {
            for (char c : s3) {
                ans.push_back(string(1,a) + b + c);
            }
        }
    }
    return ans;
}

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